Background

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.

Problem Description

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.

Input Format

The first line contains two positive integers $n,k$, as described.

The next line contains $n$ integers, representing $\{a_n\}$.

Output Format

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

4 3
-3 1 2 2

141

Hint

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

Translated by ChatGPT 5