【UNR #9】人类勇气之赞歌
在一场 UNR 结束之际，你要谱写一首人类勇气之赞歌。
给定一个长度为 $n$，元素互不相同的正整数序列 $[a_1, a_2, \dots, a_n]$ 和一个正整数 $k$。
定义 $z$ 被 $(x, y)$ 包含当且仅当：$\min(x, y) < z < \max(x, y)$。
现在你想知道，对于所有 $1 \leq m \leq n$：
- 令 $b = [a_1, a_2, \dots, a_m]$。
你需要将 $b$ 划分成若干连续段，然后每段内选出两个可以相同的元素；假设某段被选择的两个元素为 $u, v$，如果该段中不被 $(u, v)$ 包含的元素至少有 $k$ 个，那么你可以在该段获得 $(u-v)^2$ 的收益，否则你只能获得 $0$ 的收益。
你需要回答在最优的策略下，你可以获得的总收益的最大值。
输入格式
第一行输入两个正整数 $n, k$。
第二行输入 $n$ 个互不相同的正整数 $a_1, a_2, \dots, a_n$。
输出格式
输出一行共 $n$ 个数 $c_1, c_2, \dots, c_n$，其中 $c_i$ 表示 $m=i$ 时的答案。
6 2
9 8 2 4 3 5
0 1 49 49 50 53
20 3
6 15 3 18 1 12 2 16 8 9 10 14 20 11 17 19 13 5 7 4
0 0 81 144 225 225 337 340 340 386 386 386 468 468 468 514 514 612 612 664
样例三 $\sim$ 样例八
见附件下载。 它们分别对应子任务 $1$ 和 $3 \sim 7$。
限制与约定
对于所有数据，保证 $1 \leq n \leq 10^5, 2 \leq k \leq 20, 1 \leq a_i \leq 10^7$，且 $a$ 中元素互不相同。
| 子任务编号 | $n \leq$ | $k \leq$ | 分值 |
|---|---|---|---|
| $1$ | $1000$ | $20$ | $4$ |
| $2$ | $5 \times 10^4$ | $8$ | $20$ |
| $3$ | $10^5$ | $2$ | $12$ |
| $4$ | $3$ | $12$ | |
| $5$ | $5$ | $16$ | |
| $6$ | $8$ | $16$ | |
| $7$ | $20$ | $20$ |
时间限制：$8 \texttt{s}$
空间限制：$2 \texttt{GB}$