P6496 [COCI 2016/2017 #2] Nizin

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

#### 【样例解释】 使用 `[]` 标记 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](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #2](https://hsin.hr/coci/archive/2016_2017/contest2_tasks.pdf) _T3 Nizin_**。