对称合并

题目描述

数列 $\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$

输出格式

• 单个整数表示答案。

数据范围

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

样例数据 1

输入

5
1 2 4 6 1

输出

1

样例数据 2

输入

3
1 4 2

输出

2

说明

合并成一个数