Description

        小明非常喜欢回文数列。回文数列是指一个包含N个整数的数列A，分别为A[1],A[2],……,A[n]，对于第i(1<=i<=N)个数A[i]，都有A[i]=A[N-i+1]。但是回文数字非常难得到。
        现在小明想到了一个办法，他可以将数列中，任意两个相邻的数字合并，用它们的和来代替，合并完成的值还可以和其他值不断合并，直到只剩下一个数。要知道一个数肯定是回文数列。
       当然，小明希望他的回文数列尽可能长，因此，请你帮助小明计算一下，对于一个长度为N的数列，经过最少多少次合并，可以构成一个回文数列。

Input Format

第一行一个整数N，表示数列中整数的个数。
第二行包含N个正整数，中间用空格分开，表示数列中的数字。

Output Format

输出一个最小合并次数，使得数列变成回文数列。

3
1 2 3

1

Hint

【输出输出样例1】

</tr> </tbody> </table>

【样例1解释】

将1,2合并得到回文数列3 3

【输出输出样例2】

array.in	array.out
3 1 2 3 </td>	1

</tr> </tbody> </table>

【样例2解释】

将2,4合并，得到回文数列1 6 6 1

【输出输出样例3】

array.in	array.out
5 1 2 4 6 1 </td>	1

</tr> </tbody> </table>

【样例3解释】

先将1和4合并，得到5 3 2，再将3 2合并得到5 5是回文数列

【数据范围】

30%的数据，N<=10

60%的数据，N<=1000
       100%的数据，N<=1000000，a[i]<=10^9。

Source

贪心 模拟

array.in	array.out
4 1 4 3 2 </td>	2