Problem Description

Given a sequence $a_0,a_1,a_2,\dots,a_n,a_{n+1}$.

It satisfies $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$, define 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.

If $0 \le b_1,b_2,b_3,b_4,b_5,b_6 \le n+1$, and $b_i$ is adjacent to $b_{i+1}$, $b_1$ is adjacent to $b_6$, and all $b_i$ are distinct, then the set $\{b_1,b_2,b_3,b_4,b_5,b_6\}$ is called a 6-cycle (that is, when judging whether two 6-cycles are the same, the order of $b_i$ is not considered).

There are $m$ modification operations. Each operation gives $x\;y$, and changes $a_x$ to $a_x+y$.

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

Input Format

The first line contains an integer $n$.

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

The third line contains an integer $m$.

The next $m$ lines each contain two integers $x\;y$, describing one modification operation.

Output Format

Output $m$ lines. Each line contains one integer, the number of 6-cycles after each modification.

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

3
0
1
1

Hint

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

For $100\%$ of the testdata, 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$.

Translated by ChatGPT 5