P6611 [Code+#7] Hexagonal Cycle

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$.

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

| Subtask | Score | Constraints | | :-----: | :---: | :---------: | | $1$ | $10$ | $\max (n,m)\le 100$ | | $2$ | $10$ | $\max (n,m)\le 2000$ | | $3$ | $20$ | $\max (n,m)\le 50000$ | | $4$ | $20$ | for each operation, $x\le 100$ | | $5$ | $20$ | for each operation, $y\le 10$ | | $6$ | $20$ | | Translated by ChatGPT 5