数组划分

题目描述

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

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

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

输入格式

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

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

输出格式

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

数据范围

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

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

样例

输入样例 1

4
1 2 -3 4

输出样例 1

6

输入样例 2

6
-1 -1 4 -5 -1 4

输出样例 2

0