P8590 "JROI-8" This Is the Sunrise of the New Calendar, and Also the Sunset of the Old Calendar

 > The girl stands by the sea, gazing at the last glow of the setting sun.\ > "It has already passed, the year of the old calendar......" **Reprint authorization has been obtained.**

Given a sequence $\{a_n\}$ where each term is not less than the previous term. For every positive integer $m$ with $m \le k$, ask: if we split the sequence $a$ into $m$ segments (empty segments are allowed), and then for the $i$-th segment from left to right, add $i$ to every number in that segment, what is the maximum possible value of $\sum\limits_{j=1}^n a_j^2$ after the increment? Each query is independent. That is, in each query, the value added to each number does not carry over to the next query. For example, for the sequence $\{-3,1,2,2\}$, if $m=5$, one possible segmentation is $[-3][][1,2][][2]$. The resulting sequence after increment is $-2,4,5,7$, and then $\sum\limits_{j=1}^n a_j^2=94$. Let the answer for $m=i$ (i.e., the maximum $\sum\limits_{j=1}^n a_j^2$ in this case) be $q_i$. To be nice, you only need to output $\left(\sum\limits_{i=1}^k q_i\right) \bmod 998244353$. The standard solution is not based on this special output format, meaning it can compute each $q_i$ independently.

The first line contains two positive integers $n,k$, as described. The next line contains $n$ integers, representing $\{a_n\}$.

Output one integer, which is $\left(\sum\limits_{i=1}^k q_i\right) \bmod 998244353$.

#### Sample Explanation When $m=1$, the optimal strategy is $[-3,1,2,2]$, and $q_1=(-2)^2+2^2+3^2+3^2=26$. When $m=2$, the optimal strategy is $[-3][1,2,2]$, and $q_2=(-2)^2+3^2+4^2+4^2=45$. When $m=3$, the optimal strategy is $[-3][][1,2,2]$, and $q_3=(-2)^2+4^2+5^2+5^2=70$. So $\left(\sum\limits_{i=1}^k q_i\right) \bmod 998244353=(q_1+q_2+q_3)\bmod 998244353=(26+45+70)\bmod 998244353=141$. #### Constraints | Test Point ID | Score | $n\leq$ | $k\leq$ | $\lvert a_i\rvert \leq$ | Special Property | | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | | $1\sim 3$ | $15$ | $12$ | $12$ | $1000$ | None | | $4\sim 6$ | $15$ | $1000$ | $1000$ | $1000$ | None | | $7\sim 8$ | $10$ | $10^6$ | $10^6$ | $10^7$ | $a_i\geq0$ | | $9 \sim 12$ | $20$ | $10^6$ | $1000$ | $10^7$ | None | | $13\sim 20$ | $40$ | $10^6$ | $10^7$ | $10^7$ | None | Translated by ChatGPT 5