题目描述

czm 非常喜欢回文数列。回文数列是指一个包含 N 个整数的数列 A ，分别为 A[1] , A[2] ,..., A[n]，对于第 i ( 1 <= i <= N ) 个数 A[i] ，都有 A[i] = A[N-i+1] 。但是回文数字非常难得到。

现在 czm 想到了一个办法，他可以将数列中，任意两个相邻的数字合并，用它们的和来代替，合并完成的值还可以和其他值不断合并，直到只剩下一个数。要知道一个数肯定是回文数列。

当然， czm 希望他的回文数列尽可能长，因此，请你帮助 czm 计算一下，对于一个长度为 N 的数列，经过最少多少次合并，可以构成一个回文数列。

输入格式

第 1 行一个整数 N ( 1 <= N <= 500000 )，表示数列中整数的个数。

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

输出格式

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

样例

3
1 2 3

1

5
1 2 4 6 1

1

4
1 4 3 2

2