Do Geese See God? Or, Was It A Rat I Saw? Nevermind the geese or rats, this is just an unnecessary introduction to showcase Mislav's love of palindromes. Help him solve the following task!

Let $A$ be an array of $N$ integers. We say that $A$ is palindromic if for each $i$ it holds $A[i]=A[N-i+1]$, where $A[i]$ represents the $i^{\text{th}}$ element of array $A$, and the index of the first element in the array is $1$.

Mislav can modify the array in the following way: in a single move, he chooses two adjacent elements of that array and replaces them with their sum. Notice that the number of elements in the array is going to decrease by $1$ after each move. Mislav wants to know what is the least number of moves he must make in order for the original array to become palindromic.

Input Specification

The first line of input contains the integer $N$ $(1\le N\le {10}^6)$ that represents the number of elements in the array.

The following line contains $N$ space-separated positive integers that represent the elements in Mislav's array. The numbers in the input will be at most ${10}^9$.

Output Specification

Output the minimal number of moves it takes to transform the original array to a palindromic one, given the rules from the task.

Scoring

In test cases worth $30\mathrm{\%}$ of total points, it will hold $N\le 10$.

In test cases worth $60\mathrm{\%}$ of total points, it will hold $N\le 1000$.

Sample Input 1

3
1 2 3

Sample Output 1

1

Explanation for Sample Output 1

1 2 3 → 3 3

Sample Input 2

5
1 2 4 6 1

Sample Output 2

1

Explanation for Sample Output 2

1 2 4 6 1 → 1 6 6 1

Sample Input 3

4
1 4 3 2

Sample Output 3

2

Explanation for Sample Output 3

1 4 3 2 → 5 3 2 → 5 5