H. Ветер крепчает
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Похоже, спит. С таким видом, будто спасает японские самолёты от всех на свете.
— Киро Хондзё, Ветер крепчает

Во сне Дзиро снова стоит на бескрайнем зеленом лугу. Именно тут Дзиро испытывает всё новые и новые формы крыльев самолётов. Полёту мешают $$$n$$$ башен сомнений, у каждой из которых есть своя высота $$$h_i$$$.

Чтобы самолёт взлетел, нужен ветер. Авиаконструктор Капрони $$$q$$$ раз направляет поток воздуха на полосу препятствий. Каждый порыв ветра зарождается у башни с номером $$$s$$$ и обладает начальной силой $$$x$$$.

Ветер дует слева направо, испытывая каждую преграду на прочность:

  1. Если высота башни больше или равна текущей силе ветра ($$$h_i \ge x$$$), поток воздуха разбивается о стену. Ветер стихает, и полет прекращается.
  2. Если высота башни меньше текущей силы ветра ($$$h_i \lt x$$$), вдохновение побеждает сомнения: башня рушится, и её высота навсегда становится равной $$$0$$$. Но за каждую победу приходится платить: после очередного пройденного препятствия сила ветра уменьшается на $$$1$$$ (даже если башня уже разрушена, то есть ее высота равна $$$0$$$, сила ветра все равно уменьшается). После этого ветер стремится к следующей башне.

Помогите Дзиро узнать успешность испытаний для каждого потока ветра: определите, сколько башен (в том числе разрушенных) преодолел каждый из порывов.

Входные данные

В первой строке вводится единственное число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^{5}$$$) — количество башен.

Во второй строке вводятся $$$n$$$ целых чисел $$$h_1, h_2, \ldots, h_n$$$ ($$$0 \le h_i \le 10^{9}$$$) — начальные высоты башен.

В третьей строке вводится целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^{5}$$$) — количество порывов ветра.

В следующих $$$q$$$ строках записаны пары целых чисел $$$s$$$ и $$$x$$$ ($$$1 \le s \le n$$$, $$$1 \le x \le 10^{9}$$$)  — номер башни, от которой начинается путь, и сила ветра.

Выходные данные

Для каждого запроса выведите в отдельной строке одно целое число — количество башен, которые ветер преодолел (сломал или прошел сквозь уже сломанные), прежде чем остановиться.

Пример
Входные данные
5
2 1 5 3 4
3
1 4
1 1
4 6
Выходные данные
2
1
2
Примечание

Первый порыв ветра ломает первые две башни и разбивается об третью башню. Массив высот башен теперь выглядят так [0, 0, 5, 3, 4].

Второй порыв ветра пролетает первую башню и стихает.

Третий порыв ветра ломает четвертую башню, потом ломает пятую башню. Далее башен нет, поэтому порыв пролетает всего 2 башни. Массив высот теперь выглядит как [0, 0, 5, 0, 0].