Yesterday, Ignat heard about a staircase — an unusual structure in an array. It is constructed in a simple way:

For example, for the array [1, 2, 5, 1, 7], the staircase will be [1, 2, 5, 7].

Ignat learned to quickly find the staircase in the array a, but then Vadim came and decided to add a non-negative value x_i to the element at the p_i-th position for each of the next Q days. Now Ignat has to recalculate the staircase each time. Help him find the number of elements in the staircase after each change.

The first line contains an integer N — the number of elements in the original array (1 ≤ N ≤ 10⁵).

The second line contains N integers a_i — values in the original array (0 ≤ a_i ≤ 10⁹).

The third line contains an integer Q — the number of days during which Vadim modifies the elements of the array (1 ≤ Q ≤ 10⁵).

The next Q lines describe the changes with a pair of integers p_i and x_i — on the i-th day, Vadim increases a_pi by x_i (1 ≤ p_i ≤ N, 0 ≤ x_i ≤ 10⁹).

Output Q integers l_i — the number of elements in the staircase after the i-th change.

After the first change, the array will be [4, 2, 5, 1, 7], and its staircase will include the first, third, and fifth elements.

After the second change, the array will be [4, 5, 5, 1, 7], and its staircase will include the first, second, and fifth elements.

After the third change, the array will be [4, 5, 5, 7, 7], and its staircase will include the first, second, and fourth elements.