Isotonic Regression Sum of Squared Errors

You are given a sequence \(A_1, A_2, \dots, A_n\) and \(m\) independent update operations. For each scenario (the initial sequence and each update operation applied to a fresh copy of the original sequence), you must find a non‐decreasing sequence \(B_1, B_2, \dots, B_n\) which minimizes the sum

[ S = \sum_{i=1}^n (A_i - B_i)^2, ]

and then output the value of \(S\) in modular form. More precisely, note that the optimal value \(S\) is a rational number expressible in the form \(\frac{x}{y}\) with nonnegative integers \(x,y\). You are to compute and output

[ (x \times y^{p-2}) \bmod p, \quad p = 998244353, ]

where (y^{p-2}) is the modular inverse of (y) modulo (p). The sequence (B) must satisfy (B_1 \le B_2 \le \dots \le B_n>.

Note: The optimal sequence \(B\) is obtained by solving an isotonic regression problem using the pool-adjacent-violators algorithm (PAVA). In each independent update operation, you are given two integers \(i\) and \(k\) indicating that you should change \(A_i\) to \(k\) (this change is applied only for that query).

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \le n, m \le 10^5)\), representing the length of the sequence and the number of update operations.

The second line contains \(n\) integers, \(A_1, A_2, \dots, A_n\).

Each of the following \(m\) lines contains two integers \(i\) and \(k\), indicating that in this query you should change \(A_i\) to \(k\). Each query is independent (i.e. the update does not persist to the next query).

outputFormat

Output \(m+1\) lines. The first line is the answer for the initial sequence, and each of the following \(m\) lines is the answer for the corresponding independent update query. The answer for each case is defined as \((x\times y^{p-2}) \bmod p\) where \(\frac{x}{y}\) is the minimum value of \(\sum_{i=1}^n(A_i-B_i)^2\) for that case, and \(p = 998244353\) is a prime.

sample

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

499122183
5
4
499122183