C0729 数组划分

数组划分

题目描述

给定 n 个整数构成的数组 A=[a₁,a₂,...,a_n]。

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

分方案的偏差值定义为所有子段偏差值之和。

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

形式化地，你可以将 A 划分为若干非空连续子段A₁,A₂,...,A_k，使得A=A₁十A₂十...A_k，这里的 + 代表数组的连接。对于 1≤i≤k，设数组包含 mi 个整数。你需要最小化 。

输入

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

第二行，n个整数a1,a2,....an，表示数组A。

输出

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

数据范围

1≤n≤2000，-100 ≤ai≤100

输入样例1

4

1 2 -3 4

输出样例1

6

输入样例2

6

-1 -1 4 -5 -1 4

输出样例2

0