Kamui

There is a graph with a total of $2N$ vertices. There are no edges between the $1$st and $N$-th vertices, and there are no edges between the $(N+1)$-th and $2N$-th vertices. That is, the given graph is a bipartite graph.

A sequence of positive integers $a\_1, a\_2, \cdots, a\_N$ is given. For any $(i,j)$ pair with $1 \le i, j \le N$, the necessary and sufficient condition for vertices $i$ and $N+j$ to be connected is that $j \le a\_i$.

A total of $Q$ queries are given. Each query is represented by two integers $v$ and $x$, indicating that the value of $a\_v$ will be changed to $a\_v + x$. It is guaranteed that $x = 1$ or $x = -1$. For each query, you must count the number of cycles of length $4$ in the given graph. Since the count may be large, output the remainder when divided by $998\\,244\\,353$. Two cycles are considered different if the sets of edges composing them are different.

The first line contains two positive integers $N$ and $Q$, separated by a space.

The second line contains a total of $N$ integers $a\_1, a\_2, \cdots, a\_N$, separated by spaces.

The next $Q$ lines each contain two integers $v$ and $x$ separated by a space. The input on the $i$th line indicates that $a\_v$ will be changed to $a\_v + x$.

After each query is executed, output the remainder when the number of cycles of length $4$ is divided by $998\\,244\\,353$ on each line.

• $1 \le N \le 500\\,000$, $1\le Q\le 500\\,000$
• For each queries, $1 \le v \le N$ and x \in \left\\{ -1, 1 \right\\}.
• After each queries, it is guaranteed that $0\le a\_i\le N$ for all $1\le i\le N$.

The set of four edges \left\\{ xy,yz,zw,wx\right\\} in a graph is considered to be a cycle of length $4$.