配点 : $800$ 点

問題文

$N$ 項からなる正整数列 $A = (A_1, A_2, \ldots, A_N)$ と $Q$ 個のクエリが与えられます。$i$ 番目のクエリは、以下のようなものです：

• 整数 $x_i, y_i$ （ただし $1\leq x_i\leq N$）が与えられる。$A_{x_i}$ を $y_i$ に変更する。

クエリで数列が変更されるたびに、以下の問題の答えを $\mod 998244353$ で求めてください（注記参照）。

数列 $A$ に対して以下の操作を $n$ 回行うとき、獲得できる総得点の最大値を $f(n)$ とする。

• $A_i\leq A_j$ となる $i, j$ および $A_i + 2x \leq A_j$ となる非負実数 $x$ を選ぶ。
• $A_i$ に $x$ を加え、$A_j$ から $x$ を引く。
• $x$ 点を獲得する。

極限 $\displaystyle \lim_{n\to\infty} f(n)$ が存在することが証明できる。この値を求めよ。

注記

求める極限は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な $2$ つの整数 $P, Q$ を用いて $\frac{P}{Q}$ と表したとき、$R\times Q\equiv P\pmod{998244353}$ かつ $0\leq R < 998244353$ を満たす整数 $R$ がただ一つ存在することが証明できます。この $R$ を求めてください。

制約

• $2\leq N\leq 3\times 10^5$
• $1\leq Q\leq 3\times 10^5$
• $1\leq A_i \leq 10^9$
• $1\leq x_i\leq N$
• $1\leq y_i\leq 10^9$

入力

入力は以下の形式で標準入力から与えられます。

$N$ $Q$

$A_1$ $A_2$ $\ldots$ $A_N$

$x_1$ $y_1$

$\vdots$

$x_Q$ $y_Q$

出力

$Q$ 行出力してください。$i$ 行目には、$i$ 番目のクエリで数列を変更した時点での、問題の答えを出力してください。

3 4
7 5 5
1 5
2 6
1 7
3 5

0
1
2
2

$1$ つめのクエリにより、数列は $(5, 5, 5)$ へと変更されます。この場合任意の $n$ に対して $f(n) = 0$ となり、答えは $0$ となります。

$2$ つめのクエリにより、数列は $(5,6,5)$ へと変更されます。操作は例えば以下のように進行します。

• $(i,j,x) = (3,2,0.4)$ と選ぶ。数列を $(5, 5.6, 5.4)$ へ変更し、$0.4$ 点を獲得する。
• $(i,j,x) = (1,2,0.3)$ と選ぶ。数列を $(5.3, 5.3, 5.4)$ へ変更し、$0.3$ 点を獲得する。

上の方法では $2$ 回の操作により $0.7$ 点を獲得しており、$f(2) \geq 0.7$ であることがわかります。

この場合、獲得できる総得点は $1$ を超えることはなく、操作回数を増やしていき最適な方法で操作を行うことで、獲得できる総得点を限りなく $1$ に近づけることが可能であることが証明できます。したがって $\displaystyle \lim_{n\to\infty} f(n) = 1$ となります。

2 4
1 2
2 5
1 3
1 2
2 3

2
1
499122178
499122177