题目描述

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

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

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

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

输入格式

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

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

输出格式

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

5
1 2 4 6 1

1

4
1 4 3 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$。