M. Trapping Rain Water
time limit per test
5.0 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

There is a histogram represented by an integer sequence $$$a_1, a_2, \cdots, a_n$$$ of length $$$n$$$. For the $$$i$$$-th bar from left to right, its height is $$$a_i$$$ and its width is $$$1$$$.

We'll perform $$$q$$$ modifications to the histogram. The $$$i$$$-th modification can be represented by a pair of integers $$$(x_i, v_i)$$$ indicating that we'll increase the height of the $$$x_i$$$-th bar by $$$v_i$$$.

After each modification, answer the following query: Calculate how much water this histogram can trap if a heavy rain pours onto it and fills all the pits as much as possible.

More formally, given an integer sequence $$$a_1, a_2, \cdots, a_n$$$ of length $$$n$$$, the $$$i$$$-th modification will increase $$$a_{x_i}$$$ by $$$v_i$$$. After each modification, answer the following query: Let $$$f_i = \max(a_1, a_2, \cdots, a_i)$$$ and $$$g_i = \max(a_i, a_{i + 1}, \cdots, a_n)$$$, calculate

$$$$$$ \sum\limits_{i = 1}^n \left( \min(f_i, g_i) - a_i \right) $$$$$$

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:

The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$) indicating the number of bars in the histogram.

The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) where $$$a_i$$$ indicates the initial height of the $$$i$$$-th bar.

The third line contains an integer $$$q$$$ ($$$1 \le q \le 10^5$$$) indicating the number of modifications.

For the following $$$q$$$ lines, the $$$i$$$-th line contains two integers $$$x_i$$$ and $$$v_i$$$ ($$$1 \le x_i \le n$$$, $$$1 \le v_i \le 10^6$$$) indicating that the $$$i$$$-th modification increases the height of the $$$x_i$$$-th bar by $$$v_i$$$.

It is guaranteed that neither the sum of $$$n$$$ nor the sum of $$$q$$$ of all test cases will exceed $$$10^6$$$.

Output

For each modification output one line containing one integer indicating how much rain water this histogram can trap.

Example
Input
2
6
1 2 3 4 5 6
2
1 2
3 3
5
100 10 1 10 100
1
3 100
Output
1
4
180