P6496 [COCI 2016/2017 #2] Nizin

Let $A$ be an array with $n$ elements, indexed from $1 \dots n$. If for every integer $i \in [1,n]$ we have $A_i = A_{n-i+1}$, then $A$ is called a “palindrome array”. Mislav can modify an array in the following way: 1. Choose two **adjacent** elements. 2. **Replace** these two elements with one new element whose value is their sum. Now, an array is given. Please compute the minimum number of modifications needed for Mislav to turn it into a “palindrome array”.

The first line contains an integer $n$, the number of elements in the array. The next line contains $n$ integers $a_i$, the elements of the array.

One line with one integer, the minimum number of modifications Mislav needs to make.

#### Sample Explanation Use `[]` to mark the two numbers Mislav chooses in each modification. **Sample 1 Explanation** `[1 2] 3` -> `3 3`. **Sample 2 Explanation** `1 [2 4] 6 1` -> `1 6 6 1`. **Sample 3 Explanation** `[1 4] 3 2` -> `5 [3 2]` -> `5 5`. ------------ #### Constraints - For $30\%$ of the testdata, $n \leq 10$. - For $60\%$ of the testdata, $n \leq 10^3$. - For $100\%$ of the testdata, $1 \le n \le 10^6$, $1 \le a_i \le 10^9$. ------------ #### Note **Translated from [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #2](https://hsin.hr/coci/archive/2016_2017/contest2_tasks.pdf) _T3 Nizin_**。 Translated by ChatGPT 5