You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

少女于海边伫立，凝视着落日最后的余晖
“已然过去了呢，旧历的一年......”

已获得转载授权。

题目描述

给定序列 $\{a_n\}$，满足每一项都不小于前一项。对于所有不超过 $k$ 的正整数 $m$，询问如果将 $a$ 分成 $m$ 段（可以有空段），并给从前往后第 $i$ 段内的每个数都加上 $i$，增加后的 $\sum\limits_{j=1}^n a_j^2$ 最大是多少。询问相互独立，即每次询问时给每个数加的值不保留到下一次询问。

例如，对于序列 $\{-3,1,2,2\}$，若 $m=5$，则一种分段方式是 $[-3][][1,2][][2]$，增加后的序列是 $-2,4,5,7$，此时 $\sum\limits_{j=1}^n a_j^2=94$。

记 $m=i$ 时的答案（即此时最大的 $\sum\limits_{j=1}^n a_j^2$）为 $q_i$，出于良心考虑，你只需要输出 $\left(\sum\limits_{i=1}^k q_i\right) \bmod 998244353$ 即可。标准程序不基于特殊的输出方式，即能独立求出每一个 $q_i$。

输入格式

第一行两个正整数 $n,k$，同题意。

接下来一行 $n$ 个整数，表示 $\{a_n\}$。

输出格式

一行一个整数，表示 $\left(\sum\limits_{i=1}^k q_i\right) \bmod 998244353$。

4 3
-3 1 2 2

141

提示

【样例解释】

当 $m=1$ 时，最优策略是 $[-3,1,2,2]$，$q_1=(-2)^2+2^2+3^2+3^2=26$。

当 $m=2$ 时，最优策略是 $[-3][1,2,2]$，$q_2=(-2)^2+3^2+4^2+4^2=45$。

当 $m=3$ 时，最优策略是 $[-3][][1,2,2]$，$q_3=(-2)^2+4^2+5^2+5^2=70$。

则 $\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$。

【数据范围与约束】