Problem Description

There are $n$ snakes on the grassland, numbered $1, 2, \ldots , n$. Initially, each snake has a stamina value $a_i$. We say that the snake with index $x$ is stronger than the snake with index $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 duel. The duel lasts for several rounds. In each round, the strongest snake has the right to choose whether to eat the weakest snake:

1. If it chooses to eat, then the strongest snake’s stamina value decreases by the weakest snake’s stamina value. The weakest snake is eaten and leaves the subsequent duels. Then the next round starts.
2. If it chooses not to eat, the duel ends immediately.

Each snake wants to eat as many other snakes as possible in the duel, under the condition that it is not eaten (obviously, a snake will not choose to eat itself).

Now assume every snake is smart enough. Please find how many snakes will remain after the duel ends.

This problem contains multiple test cases. For the first test case, all snakes’ stamina values are given by the input. For each subsequent test case, compared to the previous test case, the stamina values of some snakes are modified as the new input.

Input Format

The first line contains a positive integer $T$, denoting the number of test cases.
Then there are $T$ test cases. For the first test case, the first line contains a positive integer $n$, and the second line contains $n$ non-negative integers representing $a_i$.
For test cases $2$ to $T$, each test case is given as follows:
The first line contains a non-negative integer $k$, denoting the number of snakes whose stamina will be modified.
The second line contains $2k$ integers. Every two integers form a pair $(x,y)$, meaning that $a_x$ is updated to $y$ in order. A position may be updated multiple times; the last update takes effect.

Output Format

Output $T$ lines. Each line contains one integer, denoting the number of snakes that survive in the end.

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

3
1

2
5
13 31 33 39 42
5
1 7 2 10 3 24 4 48 5 50

5
3

见附件中的 snakes/snakes3.in

见附件中的 snakes/snakes3.ans

见附件中的 snakes/snakes4.in

见附件中的 snakes/snakes4.ans

Hint

[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, then 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 $3$ snakes’ stamina values become $5, 6, 25$. In the first round, snake $3$ is the strongest and snake $1$ is the weakest. If it chooses to eat, then snake $3$’s stamina becomes $20$. In the second round, it is still the strongest snake and can eat snake $2$. Therefore, snake $3$ will choose to eat in both rounds, and finally only $1$ snake survives.

[Constraints]

For $20\%$ of the testdata, $n = 3$.
For $40\%$ of the testdata, $n \le 10$.
For $55\%$ of the testdata, $n \le 2000$.
For $70\%$ of the testdata, $n \le 5 \times {10}^4$.
For $100\%$ of the testdata: $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 for each test case (including after all modifications), the sequence $a_i$ is in non-decreasing order.

Translated by ChatGPT 5