Making the Array Palindromic

Merge adjacent elements (each merge sums them) so the resulting array reads the same forwards and backwards, using the fewest merges. All values are positive.

Medium5Two pointersGreedyArrayPrefix sumInterviewNo attempts yetTime limit1sMemory limit64 MB

Description

Examples3

Problem

Mislav likes palindromes. You are given an array $A$ of $N$ integers. The array is palindromic if $A[i] = A[N-i+1]$ holds for every $i$ , where the first element of the array has index 1.

In one move Mislav can pick two adjacent elements of the array and replace them with their sum. Each move decreases the number of elements by 1. For example, merging the first two elements of $[1, 2, 3]$ gives $[3, 3]$ .

Find the least number of moves needed to turn the original array into a palindromic one.

Input

The first line contains the integer $N$ , the number of elements in the array ( $1 \le N \le 10^6$ ).

The second line contains $N$ space-separated positive integers, the elements of the array. Each element is at most $10^9$ .

Output

Print the minimal number of moves needed to make the array palindromic.