Given a sequence $a_0, a_1, a_2, \dots, a_n, a_{n+1}$, where $a_0 = a_{n+1} = +\infty$, and $a_1, a_2, \dots, a_n$ are given in the input.

For $1 \le x \le n$, we say that $\max_{0 \le i < x, a_i \ge a_x} i$ and $x$ are adjacent, and $\min_{x < i \le n+1, a_i > a_x} i$ and $x$ are adjacent.

If $x$ and $y$ are adjacent, then $y$ and $x$ are also adjacent.

A set $\{b_1, b_2, b_3, b_4, b_5, b_6\}$ is called a 6-cycle if $0 \le b_1, b_2, b_3, b_4, b_5, b_6 \le n+1$, $b_i$ and $b_{i+1}$ are adjacent for $1 \le i \le 5$, $b_1$ and $b_6$ are adjacent, and all $b_i$ are distinct (i.e., the order of $b_i$ is not considered when determining if two 6-cycles are the same).

There are $m$ modification operations. Each operation provides $x$ and $y$, and updates $a_x$ to $a_x + y$.

After each modification, output the number of 6-cycles.

Input

The first line contains an integer $n$.

The second line contains $n$ integers representing $a_1, a_2, \dots, a_n$.

The third line contains an integer $m$.

The next $m$ lines each contain two integers $x$ and $y$, representing a modification operation.

Output

Output $m$ lines, each containing an integer representing the number of 6-cycles after each modification.

Examples

Input 1

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

Output 1

3
0
1
1

Subtasks

Idea: ccz181078, Solution: ccz181078, Code: ccz181078 & zx2003, Data: nzhtl1477 & zx2003

For $100\%$ of the data, all values mentioned above are integers, and $1 \le n, m \le 5 \cdot 10^5$; $1 \le x \le n$; $1 \le a_i, y \le 10^9$.