Chtholly wants you to maintain a sequence of $n$ positive integers $a_1, a_2, \ldots, a_n$ and supports modifying the value at a specific position in the sequence.

After each modification, determine how many operations are required to make the entire sequence all $0$s by repeatedly performing the following operation (the sequence remains unchanged after the query and does not actually become all $0$s):

Select the position of the maximum value in the sequence. If there are multiple maximum values, choose the one with the smallest index. Let this position be $x$. Then, decrease the values of $a_{x-1}, a_x, a_{x+1}$ by $1$. If any value in the sequence becomes less than $0$, set it to $0$.

Input

The first line contains an integer $n$.

The next $n$ lines each contain an integer $a_i$.

The next line contains an integer $q$.

The next $q$ lines each contain two space-separated integers $x_i$ and $y_i$, representing that $a_{x_i}$ is modified to $y_i$.

Output

Output $q$ lines, each containing an integer representing the answer.

Examples

Input 1

4
3
6
6
4
3
4 4
3 5
1 8

Output 1

10
10
13

Note

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078

$1\leq n,q\leq 10^5$, $1\leq x_i\leq n$, $1\leq a_i,y_i\leq 10^9$.