Description

qwqwq.

Given a sequence $a_0, a_1, \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$, define $\max_{0 \le i < x, a_i \ge a_x} i$ and $x$ to be adjacent, and define $\min_{x < i \le n+1, a_i > a_x} i$ and $x$ to be 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 pairwise distinct, then the set $\{b_1, b_2, b_3, b_4, b_5, b_6\}$ is called a hexagonal cycle (that is, when judging whether two hexagonal 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 hexagonal cycles.

All values mentioned above are integers, and $1 \le n, m \le 5 \times 10^5$, $1 \le x \le n$, $1 \le a_i, y \le 10^9$.

Input Format

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\ y$, representing one modification operation.

Output Format

Output $m$ lines, each containing one integer, representing the number of hexagonal 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

Translated by ChatGPT 5