该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定 $n$ 个整数构成的数组 $A=[a_1,a_2,\ldots,a_n]$。

你需要将数组 $A$ 划分为若干非空连续子段。对于划分得到的某个子段，它的偏差值定义为子段内整数和的平方。划分方案的偏差值定义为所有子段偏差值之和。

你需要最小化划分方案的偏差值。

形式化地，你可以将 $A$ 划分为若干非空连续子段 $A_1,A_2,\ldots,A_k$，使得 $A=A_1+A_2+\ldots+A_k$，这里的 $+$ 代表数组的连接。对于 $1\le i\le k$，设数组 $A_i=[a_1^{(i)},\ldots,a_{m_i}^{(i)}]$ 包含 $m_i$ 个整数。你需要最小化 $\sum_{i=1}^{k}\left(\sum_{j=1}^{m_i}a_j^{(i)}\right)^2$。

输入格式

第一行，一个正整数 $n$，表示数组 $A$ 的长度。

第二行，$n$ 个整数 $a_1,a_2,\ldots,a_n$，表示数组 $A$。

输出格式

一行，一个整数，表示划分方案偏差值的最小值。

样例 #1

样例输入 #1

4
1 2 -3 4

样例输出 #1

6

样例 #2

样例输入 #2

6
-1 -1 4 -5 -1 4

样例输出 #2

0

提示

【样例解释 1】

把数组划分为 $[1]$、$[2]$、$[-3,4]$ 三段，偏差值为 $1^2+2^2+(-3+4)^2=1+4+1=6$，这是最小的。

【样例解释 2】

整个数组的元素和为 $(-1)+(-1)+4+(-5)+(-1)+4=0$，直接作为一段的偏差值就是 $0^2=0$，不可能更小。

【数据范围】

对于 $40\%$ 的测试点，保证 $0\le a_i\le 50$。

对于所有测试点，保证 $1\le n\le 2000$，$-100\le a_i\le 100$。