34658번 - Kamui 다국어

문제

There is a graph with a total of 2ドルN$ vertices. There are no edges between the 1ドル$st and $N$-th vertices, and there are no edges between the $(N+1)$-th and 2ドルN$-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ドル$.