Вчера Игнат услышал про лестницу — необычную структуру в массиве. Она строится простым образом:

Например, для массива [1, 2, 5, 1, 7] лестницей будет [1, 2, 5, 7].

Игнат научился быстро находить лестницу в массиве a, но тут пришёл Вадим, который в каждый из следующих Q дней решил прибавлять к элементу на p_i-м месте неотрицательное значение x_i. Теперь Игнату приходится каждый раз пересчитывать лестницу. Помогите ему найти количество элементов в лестнице после каждого изменения.

В первой строке дано целое число N — количество элементов в исходном массиве (1 ≤ N ≤ 10⁵).

Во второй строке даны N целых чисел a_i — значения в исходном массиве (0 ≤ a_i ≤ 10⁹).

В третьей строке дано целое число Q — количество дней, в течение которых Вадим изменяет элементы массива (1 ≤ Q ≤ 10⁵).

В следующих Q строках описаны изменения парой целых чисел p_i и x_i — в i-й день Вадим увеличивает a_pi на x_i (1 ≤ p_i ≤ N, 0 ≤ x_i ≤ 10⁹).

Выведите Q целых чисел l_i — количество элементов в лестнице после i-го изменения.

После первого изменения массив будет равен [4, 2, 5, 1, 7], в его лестницу будут входить первый, третий и пятый элементы.

После второго изменения массив будет равен [4, 5, 5, 1, 7], в его лестницу будут входить первый, второй и пятый элементы.

После третьего изменения массив будет равен [4, 5, 5, 7, 7], в его лестницу будут входить первый, второй и четвёртый элементы.