{"raw_statement":[{"iden":"background","content":"![1663764375173.png](https://img-kysic-1258722770.file.myqcloud.com/8c10be566f21cceb653f209300936b97/68a6764e14651.png)\n\n>少女于海边伫立，凝视着落日最后的余晖\\\n“已然过去了呢，旧历的一年......”\n\n**已获得转载授权。**"},{"iden":"statement","content":"给定序列 $\\{a_n\\}$，满足每一项都不小于前一项。对于所有不超过 $k$ 的正整数 $m$，询问如果将 $a$ 分成 $m$ 段（可以有空段），并给从前往后第 $i$ 段内的每个数都加上 $i$，增加后的 $\\sum\\limits_{j=1}^n a_j^2$ 最大是多少。询问相互独立，即每次询问时给每个数加的值不保留到下一次询问。\n\n例如，对于序列 $\\{-3,1,2,2\\}$，若 $m=5$，则一种分段方式是 $[-3][][1,2][][2]$，增加后的序列是 $-2,4,5,7$，此时 $\\sum\\limits_{j=1}^n a_j^2=94$。\n\n记 $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"},{"iden":"input","content":"第一行两个正整数 $n,k$，同题意。\n\n接下来一行 $n$ 个整数，表示 $\\{a_n\\}$。"},{"iden":"output","content":"一行一个整数，表示 $\\left(\\sum\\limits_{i=1}^k q_i\\right) \\bmod 998244353$。"},{"iden":"note","content":"#### 【样例解释】\n\n当 $m=1$ 时，最优策略是 $[-3,1,2,2]$，$q_1=(-2)^2+2^2+3^2+3^2=26$。\n\n当 $m=2$ 时，最优策略是 $[-3][1,2,2]$，$q_2=(-2)^2+3^2+4^2+4^2=45$。\n\n当 $m=3$ 时，最优策略是 $[-3][][1,2,2]$，$q_3=(-2)^2+4^2+5^2+5^2=70$。\n\n则 $\\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$。\n\n#### 【数据范围与约束】\n\n| 测试点编号 | 分数 | $n\\leq$ | $k\\leq$ | $\\lvert a_i\\rvert \\leq$ | 特殊性质 |\n| -----------: | -----------: | -----------: | -----------: | -----------: | -----------: |\n| $1\\sim 3$ | $15$ | $12$ | $12$ | $1000$ | 无 |\n| $4\\sim 6$ | $15$ | $1000$ | $1000$ | $1000$ | 无 |\n| $7\\sim 8$ | $10$ | $10^6$ | $10^6$ | $10^7$ | $a_i\\geq0$ |\n| $9 \\sim 12$ | $20$ | $10^6$ | $1000$ | $10^7$ | 无 |\n| $13\\sim 20$ | $40$ | $10^6$ | $10^7$ | $10^7$ | 无 |\n"}],"translated_statement":null,"sample_group":[["4 3\n-3 1 2 2","141"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}