题目描述

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

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

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

输入格式

第一行一个整数 N，表示数列中整数的个数。

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

输出格式

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

3
1 2 3

1

</p>

提示

样例解释 1：将 1,2 合并得到回文数列 3 3。

样例解释 2：将 2,4 合并，得到回文数列 1 6 6 1。

数据范围：50% 的数据 N≤1000；100% 的数据 N≤1000000，a[i]≤10^9。

输入：
5
1 2 4 6 1
输出：
1

输入：
4
1 4 3 2
输出：
2

本题共 8 个测试点。

来源

贪心专题