题目描述

数列 $\alpha_1,\alpha_2,\dots, \alpha_n$ 的逆转定义为 $\alpha_n,\alpha_{n-1},\dots, \alpha_1$。

如果一个数列与它的逆转完全一样，则称该数列对称。

例如 $1,2,2,1$ 以及 $123, 456, 123$ 都是对称的，但 $121, 212$ 不是。

给定一个数列 $A_1, A_2,\dots,A_N$，请问至少需要进行几次合并操作，才能将这个数列变成对称？

所谓合并操作就是在数列中选择两个相邻的数字，删除它们，然后将它们的和插入到删除的位置。

输入格式

• 第一行：单个整数表示 $N$
• 第二行：$N$ 个整数表示 $A_1,A_2,\dots,A_N$

输出格式

• 单个整数表示答案。

5
1 2 4 6 1

1

3
1 4 2

2

样例解释 2

合并成一个数

数据范围

• 对于 $30\%$ 的数据，$N \leq 10$。
• 对于 $60\%$ 的数据，$N \leq 10^3$。
• 对于 $100\%$ 的数据，$1\le N\le 10^6$
• $1\le A_i\le 10^9$。