문제

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

입력

The first line of input contains the integer N (1 ≤N ≤ $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 the minimal number of moves it takes to transform the original array to a palindromic one, given the rules from the task.

채점

In test cases worth 30% of total points, it will hold N ≤ 10. In test cases worth 60% of total points, it will hold N ≤ 1 000.

예제 입력 1

3
1 2 3

예제 출력 1

1

예제 입력 2

5
1 2 4 6 1

예제 출력 2

1

예제 입력 3

4
1 4 3 2

예제 출력 3

2