时间限制：1秒　　内存限制：256M

---

题目描述

设 \(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 至少需要修改数组的次数。

输入输出样例 #1

输入 #1

3
1 2 3 

输出 #1

1 

输入输出样例 #2

输入 #2

5
1 2 4 6 1

输出 #2

1 

输入输出样例 #3

输入 #3

4
1 4 3 2 

输出 #3

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\)。

---