“Do Geese See God?”（大雁能看到上帝吗？）或者 “Was It A Rat I Saw?”（我看到的是一只老鼠吗？）。别管大雁还是老鼠了，这只是一个用来展示 Mislav 对回文的热爱的无用引入。帮他解决以下任务吧！

设 $A$ 是一个含有 $N$ 个整数的数组。如果对于每个 $i$，都有 $A[i] = A[N-i+1]$ 成立，我们就说 $A$ 是回文的。其中 $A[i]$ 表示数组 $A$ 的第 $i$ 个元素，且数组中第一个元素的下标为 $1$。

Mislav 可以通过以下方式修改数组：在单次操作中，他选择该数组中的两个相邻元素，并用它们的和来替换它们。注意，每次操作后，数组中的元素个数都会减少 $1$。Mislav 想知道，为了使原始数组变成回文数组，他最少需要进行多少次操作。

输入格式

输入的第一行包含整数 $N$（$1 \le N \le 10^6$），表示数组中元素的个数。

第二行包含 $N$ 个空格分隔的正整数，表示 Mislav 数组中的元素。输入中的数字最大为 $10^9$。

输出格式

输出根据任务规则将原始数组转换为回文数组所需的最少操作次数。

子任务

• 对于 $30\%$ 的测试数据，满足 $N \le 10$。
• 对于 $60\%$ 的测试数据，满足 $N \le 1000$。

样例

输入样例 1

3
1 2 3

输出样例 1

1

输入样例 2

5
1 2 4 6 1

输出样例 2

1

输入样例 3

4
1 4 3 2

输出样例 3

2

说明

样例解释：

• 1 2 3 $\to$ 3 3
• 1 2 4 6 1 $\to$ 1 6 6 1
• 1 4 3 2 $\to$ 5 3 2 $\to$ 5 5