题目描述

给定一个由 $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$。

每当通过查询修改数列后，请求出下述问题的答案，并对 $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$ 次查询修改数列后的答案。

样例 1

输入

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

输出

0
1
2
2

样例 2

输入

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

输出

2
1
499122178
499122177

说明/提示

注记

所求极限一定是有理数。在本题的约束下，若用互质的两个整数 $P, Q$ 表示该值为 $\frac{P}{Q}$，则存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 998244353$。请输出这个 $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$

样例解释 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$。

由 ChatGPT 4.1 翻译