给定 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。

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

数据范围

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

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

GESP六级26年9月