Duel of the Snakes

On a vast grassland, there are (n) snakes numbered (1,2,\ldots,n). Initially, snake (i) has a stamina value (a_i). We define that snake (x) is stronger than snake (y) if and only if (a_x > a_y) or (a_x = a_y) and (x > y).

The snakes then engage in a duel that proceeds in rounds. In each round, the current strongest snake (according to the order above) has the right to choose whether to eat the weakest snake (the snake with the least strength, where ties are broken by the smaller index). If it chooses to eat, its stamina is decreased by the stamina of the weakest snake, i.e. it becomes (a_x - a_y), and the weakest snake is removed from the duel. The duel then continues with the next round. If it chooses not to eat, the duel ends immediately.

Every snake wants to maximize the number of other snakes it eats, under the sole condition that it is not eaten itself. Assume that all snakes are extremely intelligent so that none will take an action that eventually leads to its own demise. Your task is to determine, for a given configuration, how many snakes remain at the end of the duel.

Note that the input consists of multiple test cases. For the first test case, the stamina values for all (n) snakes are provided. For each subsequent test case, the input specifies modifications to some snakes’ stamina values relative to the configuration from the previous test case. For each configuration (the initial one and after every modification group), the duel is simulated independently.

inputFormat

The input begins with an integer (n) denoting the number of snakes. The next line contains (n) integers (a_1, a_2, \ldots, a_n) representing the initial stamina values. The following line contains an integer (q) representing the number of modification groups.

Each of the next (q) groups describes a new test case as follows:

• The first line of the group contains an integer (k), the number of modifications.
• Then (k) lines follow, each containing two integers (i) and (v) meaning that the stamina value of snake (i) is updated to (v).

For each test case (the initial configuration and after every modification group), simulate the duel as described and output the number of snakes remaining at the end (each on a new line).

outputFormat

For each test case, output a single integer on a separate line – the number of snakes remaining at the end of the duel.

sample

3
5 3 5
2
1
1 1
2
2 6
3 2

3
1
1