Description

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”.

Input Format

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.

Output Format

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

3
1 2 3 

1 

5
1 2 4 6 1

1 

4
1 4 3 2 

2 

Hint

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 CONTEST #2 T3 Nizin。

Translated by ChatGPT 5