[ARC126E] Infinite Operations

给定一个长度为 $n$ 的正整数序列 $a$ 和 $q$ 个操作，第 $i$ 个操作为如下： - 给定 $x,y$，将 $a_x\to y$ 每一次操作后输出这个序列的最大价值，价值定义如下：每一次选择 $i,j$ 满足 $a_i\le a_j$，找到一个非负实数 $x$ 满足 $a_i+2x\le a_j$，将 $a_i\to a_i+x,a_j\to a_j-x$，得到 $x$ 的价值，价值可以累加。你可以重复这个操作多次。可以证明最大的总价值收敛到一个有理数，输出这个有理数对 $998244353$ 取模的值。 - $2\le n,q\le 3\times 10^5,a_i\le 10^9$

[problemUrl]: https://atcoder.jp/contests/arc126/tasks/arc126_e $ 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) $ が存在することが証明できる。この値を求めよ。

入力は以下の形式で標準入力から与えられます。 > $ 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

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

2
1
499122178
499122177

### 注記 求める極限は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な $ 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 $ ### Sample Explanation 1 $ 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 $ となります。