题目描述

设 $A$ 是一个含有 $n$ 个元素的数组，其中各元素的编号为 $1\dots n$。若对于任意整数 $i\in [1,n]$ 都有 $A_i=A_{n-i+1}$，则称 $A$ 是一个「回文数组」。

Mislav 可以通过以下方式修改一个数组：

1. 选择两个相邻的元素。
2. 将这两个元素替换为一个新的元素，值为它们的和。

现在，给出一个数组。请你计算在至少多少次修改后，Mislav 可以将其修改为一个「回文数组」。

输入格式

第一行一个整数 $n$，表示数组中元素的个数。

接下来一行 $n$ 个整数 $a_i$，表示数组中的元素。

输出格式

一行，一个整数，表示 Mislav 至少需要修改数组的次数。

3
1 2 3 

1 

5
1 2 4 6 1

1 

4
1 4 3 2 

2 

提示

【样例解释】

使用 [] 标记 Mislav 修改时所选择的两个数。

样例 1 解释

[1 2] 3 -> 3 3。

样例 2 解释

1 [2 4] 6 1 -> 1 6 6 1。

样例 3 解释

[1 4] 3 2 -> 5 [3 2] -> 5 5。

【数据规模与约定】

• 对于 $30\%$ 的数据，保证 $n \leq 10$。
• 对于 $60\%$ 的数据，保证 $n \leq 10^3$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 10^6$，$1\le a_i\le 10^9$。

【说明】

题目译自 COCI2016-2017 CONTEST #2 T3 Nizin。