Background

qwqwq

Description

We have a sequence $a_0,a_1,a_2\dots,a_n,a_{n+1}$, satisfies $a_0=a_{n+1}=+\infty$, and $a_1,a_2,\dots,a_n$ are given from input. For $1\le x \le n$，we say $\max_{0\le ia_x} i$ and $x$ are adjacent； If $x$ and $y$ are adjacent，then $y$ and $x$ are adjacent. If $0\le b_1,b_2,b_3,b_4,b_5,b_6\le n+1$, and $b_i$ and $b_{i+1}$ are adjacent, $b_1$ and $b_6$ are adjacent, $b_i$ are distinct, then we say $\{b_1,b_2,b_3,b_4,b_5,b_6\}$ is a six-membered ring (we don't care about the order of $b_i$). There are $m$ operations. In each operation with parameters $x\;y$, $a_x$ is changed to $a_x+y$. After each operation, you should output the number of six-membered ring. All parameters above are integers. $1\le n,m\le 5\cdot 10^5;\;1\le x\le n;\;1\le a_i,y\le 10^9$.

Input Format

Read from standard input.

In the first line, there is an integer $n$. In the second line, there are $n$ integers representing $a_1\;a_2\;\dots\;a_n$. In the third line, there is an integer $m$. In the next $m$ lines, each line contains two integers $x\;y$, representing the parameters of an operation.

Output Format

Write to the standard output.

You should output $m$ lines, each line contains an integer: the number of six-membered ring after an operation.

Sample

Input

6
1 2 5 4 3 6
4
1 8
3 6
5 10
2 7

Output

3
0
1
1

Subtasks