Description

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 Format

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 Format

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

2
6
1 2 3 4 5 6
2
1 2
3 3
5
100 10 1 10 100
1
3 100

1
4
180