1 \(s / 64\) \(MB / 100\) points

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.

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.

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\) spa\(ce-se\)parated 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.

생성자가 기록되지 않았습니다.

출처 COCI 2016/2017 Contest 2