Problem Description

Let $A$ be an array containing $n$ elements, where each element is numbered from $1$ to $n$. If for any integer $i \in [1, n]$, $A_i = A_{n-i+1}$, then $A$ is called a "palindrome array".

Mislav can modify an array using the following method:

1. Select two adjacent elements.
2. Replace these two elements with a new element, whose value is their sum.

Given an array, calculate the minimum number of modifications Mislav needs to make it a "palindrome array".

Input Format

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

The next line contains $n$ integers $a_i$, representing the elements of the array.

Output Format

A single line containing an integer, representing the minimum number of modifications Mislav needs to make the array a "palindrome array".

Sample Input and Output

Sample Input #1

3
1 2 3

Sample Output #1

1

Sample Input #2

5
1 2 4 6 1

Sample Output #2

1

Sample Input #3

4
1 4 3 2

Sample Output #3

2

Notes

Sample Explanation

Using [] to mark the two numbers Mislav chooses to modify.

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.

Data Constraints

• For $30\%$ of the data, $n \leq 10$.
• For $60\%$ of the data, $n \leq 10^3$.
• For $100\%$ of the data, $1 \leq n \leq 10^6$, $1 \leq a_i \leq 10^9$.

Notes

Translated from COCI2016-2017 CONTEST #2 T3 Nizin.

见题面 Input 部分

见题面 Output 部分