Description
小明非常喜欢回文数列。回文数列是指一个包含N个整数的数列A，分别为A【1】，A【2】......，A【n】，对于第i（1<=i<=N）个数A【i】,都有A【i】=A【N-i+1】。但是回文数列是非常难得到的。
现在小明想到了一个办法，他可以将数列中，任意两个相邻的数合并，用它们的和来代替，合并完成的值还可以和其它值不断合并，直到只剩下一个数。要知道一个数肯定是回文数列。
当然，小明希望他的回文数列尽可能长，因此，请你帮助小明计算一下，对于一个长度为N的数列，经过最少多少次合并，可以构成一个回文数列。
Input
第一行一个整数N，表示数列中整数的个数。
第二行包含N个正整数，中间用空格分开，表示数列中的数。
Output
输出一个整数，表示最小合并次数，使得数列变成回文数列。
输入样例一：
6
1 2 4 5 6 1
输入样例二：
4
1 4 3 2
输入样例三：
4
3 7 3 4
输出样例一：
1
样例1解释：
将2和4合并，得到回文数列1 6 5 6 1
输出样例二：
2
样例2解释：
先将1和4合并，得到5 3 2，再将3和2合并得到5 5，是回文数列。
输出样例三：
3
样例3解释：
将4个数合并成1个数17，1个数也是回文数列。