Person in Charge

Problem Description

There are $n$ snakes on the grassland, numbered from $1$ to $n$. Initially, each snake has a stamina value $a_i$. We say that the snake numbered $x$ is stronger than the snake numbered $y$ if and only if their current stamina values satisfy $a_x > a_y$, or $a_x = a_y$ and $x > y$.

Next, these snakes will engage in a duel that lasts several rounds. In each round, the strongest snake has the option to either eat or not eat the weakest snake:

1. If it chooses to eat, the stamina value of the strongest snake will be reduced by the stamina value of the weakest snake. The weakest snake is eaten and withdraws from subsequent duels. Then the next round of the duel begins.
2. If it chooses not to eat, the duel ends immediately.

Each snake aims to eat as many other snakes as possible in the duel on the premise that it does not get eaten (obviously, a snake will not choose to eat itself).

Assuming all snakes are sufficiently intelligent, please find the number of snakes remaining after the duel ends.

There are multiple test cases for this problem. For the first test case, the stamina of each snake is fully given in the input. For each subsequent test case, the stamina of some snakes is modified relative to the previous test case as the new input.

Input Format

The first line contains a positive integer $T$, representing the number of test cases.
Next are $T$ test cases:

• For the first test case:
  • The first line contains a positive integer $n$.
  • The second line contains $n$ non-negative integers representing $a_i$.
• For the second to the $T$-th test case:
  • The first line contains a non-negative integer $k$, representing the number of snakes whose stamina is modified.
  • The second line contains $2k$ integers, where each pair of integers forms a tuple $(x, y)$, indicating that the value of $a_x$ is changed to $y$ in sequence. A position may be modified multiple times, and the last modification shall prevail.

Output Format

Output $T$ lines, each containing an integer representing the number of snakes that survive in the end.

Samples

2
3
11 14 14
3
1 5 2 6 3 25

3
1

Sample 1 Explanation

In the first test case: In the first round, snake 3 is the strongest and snake 1 is the weakest. If snake 3 chooses to eat, it will be eaten by snake 2 in the second round. Therefore, snake 3 chooses not to eat in the first round, and all 3 snakes survive.

For the second test case: The stamina values of the three snakes become $5, 6, 25$. In the first round, snake 3 is the strongest and snake 1 is the weakest. If it chooses to eat, its stamina value becomes $20$, and it is still the strongest snake in the second round and can eat snake 2. Therefore, snake 3 will choose to eat in both rounds, and only 1 snake survives in the end.

Sample 2

See snake/snake2.in and snake/snake2.ans in the contestant's directory.

Sample 3

See snake/snake3.in and snake/snake3.ans in the contestant's directory.

Sample 4

See snake/snake4.in and snake/snake4.ans in the contestant's directory.

Data Range

• For $20\%$ of the data: $n = 3$.
• For $40\%$ of the data: $n \le 10$.
• For $55\%$ of the data: $n \le 2000$.
• For $70\%$ of the data: $n \le 5 \times 10^4$.
• For $100\%$ of the data: $3 \le n \le 10^6$, $1 \le T \le 10$, $0 \le k \le 10^5$, $0 \le a_i, y \le 10^9$. It is guaranteed that the $a_i$ values of each test case (after all modifications are completed) are in non-decreasing order.