Description

你有一个非递减长度为 $n$ 的序列 $a$，可以进行如下操作。对于当前长度为 $m$ 的序列，每次操作分为两步第一步：选取一个下标 $i$，删掉 $a_i$(同时，序列长度 $m-1$),或者什么都不做第二步：选择一个下标 $j$，将 $a_j$ 改成任意一个整数。现要求进行每次操作后都要满足序列非递减。现在你想知道进行 $k$ 次操作之后，得到的序列长度为 $m$。求 $\sum_{i=2}^m(a_i-a_{i-1})^2$ 的最大值。你需要回答每个 $k$($1\le k \le n$) 的结果 ，不同的查询相互独立。

Input Format

第一行一个整数 $n$，表示数组的长度 $n$($1 \le n \le 100$)第二行 $n$ 个整数，$a_1、a_2……a_n$($-10^9 \le a_i \le 10^9$)

Output Format

输出 $n$ 行，每行一个整数。第 $i$ 行的整数表示当 $k=i$ 时候的结果。

5
1 2 3 4 5

10
16
16
16
16

Source

Online Judge http://127.0.0.1