h2. Date de intrare
Fișierul de intrare $avioane.in$ ...
Fișierul de intrare $avioane.in$ conține pe prima linie $N$ = numărul de zone și $Q$ = numărul de lansări, separate printr-un spațiu. Pe cea de-a doua linie se află $N$ numere naturale, separate prin câte un spațiu, reprezentând înălțimile $Y[~1~], Y[~2~], ..., Y[~N~]$ ale zonelor de luptă. Pe liniile 3, 4, ..., $Q$ + 2 se află câte două numere naturale $P$ și $H$ reprezentând poziția și respectiv înălțimea corespunzătoare fiecărei lansări.
h2. Date de ieșire
În fișierul de ieșire $avioane.out$ ...
Fișierul de ieșire $avioane.out$ va conține $Q$ linii. Pe fiecare dintre acestea se va afla numărul de zone care pot fi văzute la lansarea corespunzătoare: pe linia 1 se va afla numărul de zone văzute de primul avion, pe linia 2 numărul de zone văzute de cel de-al doilea avion etc.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 1.000.000$
* $1 ≤ Q ≤ 1.000.000$
* $0 ≤ Y[~i~] ≤ 1.000.000.000$, pentru fiecare $1 ≤ i ≤ N$
* $1 ≤ P ≤ N$ pentru fiecare poziție de lansare $P$
* $0 ≤ H ≤ 1.000.000.000$ pentru fiecare înălțime la care va zbura un avion, înălțime calculată față de cea a punctului de lansare
h2. Exemplu
table(example).
|_. avioane.in |_. avioane.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 4
4 0 5 7 3
3 2
2 1
4 1
2 1000000000
| 3
1
5
5
|
h3. Explicație
...
Avionul lansat de pe poziția 3 ajunge la înălțimea 5 + 2 = 7, de unde poate vedea zonele 1, 2, și 3. El nu poate survola zona 4.
Al doilea avion, lansat de pe poziția 2, ajunge la înălțimea 0 + 1 = 1, de unde nu vede decât zona 2.
Al treilea avion, lansat de pe poziția 4, ajunge la înălțimea 7 + 1 = 8, de unde vede toate zonele.
Al patrulea avion, lansat de pe poziția 2, ajunge la înălțimea 0 + 1000000000 = 1000000000, de unde vede toate zonele.
== include(page="template/taskfooter" task_id="avioane") ==
