题目描述

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

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

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

形式化地，你可以将 A 划分为若干非空连续子段 A_1,A_2,…,A_k，使得 A=A_1+A_2+…+A_k，这里的 + 代表数组的连接。对于 1≤i≤k，设数组 A_i 包含 m_i 个整数。你需要最小化所有子段元素和的平方之和。

输入格式

第一行，一个正整数 n，表示数组 A 的长度。第二行，n 个整数 a_1,a_2,…,a_n，表示数组 A。

输出格式

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

样例

样例输入 1

4
1 2 -3 4

样例输出 1

6

样例输入 2

6
-1 -1 4 -5 -1 4

样例输出 2

0

数据范围

对于 40% 的测试点，保证 0≤a_i≤50；对于所有测试点，保证 1≤n≤2000，−100≤a_i≤100。