402985: GYM100960 G Youngling Tournament

Yoda, the Grand Master of the Jedi Order, hit on the idea to hold a tournament among younglings. He has not chosen the date yet, but he has already decided on the format of the tournament.

There are N younglings studying in the Jedi Temple. Yoda can feel the Force inside younglings, moreover, he can represent the amount of the Force inside i-th youngling as the number f_i.

Therefore, the format of the tournament is the following. At first, Yoda makes the children stand in a row in order of non-increasing f_i. Then, the first youngling in the row competes against all the others united together. The combat is based on lightsaber battle and is very spectacular. However, Yoda knows that the result doesn't depend on anything but the Force inside competitors. The youngling wins if his amount of Force is not less than the total amount of the Force inside all his opponents. In that case, he is considered one of the winners. Otherwise, he loses. Anyway, after that he is removed from the row, and the tournament continues. Again, the strongest (first in the row) youngling competes against all the others standing in the row in the same format, if he wins, he is also considered one of the winners. After that he is removed and the tournament continues in the same format until there is only one child in the row. He becomes one of the winners automatically and the tournament finishes.

Yoda wants to know the total number of winners. However, as the tournament is postponed again and again, the amount of the Force inside the younglings changes from time to time. Help Yoda to compute the total number of winners after each change.

The first line of input contains a single integer N, the number of younglings in the Jedi Temple (1 ≤ N ≤ 100 000).

The second line contains N integers f₁, f₂, ..., f_N the amount of the Force inside the younglings (1 ≤ f_i ≤ 10¹²).

The third line of the input contains a single integer M, the number of changes in the Force amounts of students (0 ≤ M ≤ 50 000).

The next M lines contain information about the changes. The i-th of these lines describes the i-th change and contains two integers k and f_k * , which mean that the amount of the Force inside the k-th youngling becomes equal to f_k *  (1 ≤ k ≤ N, 1 ≤ f_k *  ≤ 10¹²).

Print M + 1 lines, each of them containing a single integer.

On the first line, print the number of winners if the tournament was held before all the changes. On line (i + 1) for all i > 0, print the number of winners if the tournament was held after the first i changes.

3
2 1 3
3
1 3
2 7
3 5

3
2
3
2

7
2 14 14 15 5 2 5
5
5 2
4 12
5 4
3 10
7 9

4
3
3
3
3
4