The War of the "tsiflikades"

Two wealthy landowners (tsiflikades) are the cause of a major headache for the king. They quarrel with each other to acquire more fields, and this story is not going to end well. The king takes on the task of finding a solution to their dispute and asks for your help.

On the road that connects the two farms ("tsiflikia"), there are N fields. We know the economic data of each field, represented by integers ~\mathbf{x_1}~, ~\mathbf{x_2}~, ..., ~\mathbf{x_N}~. Some fields generate profit, so ~\mathbf{x_i} ~ > 0, others incur losses, so ~\mathbf{x_i}~ < 0, and some have neither profit nor loss, so ~\mathbf{x_i} ~ = 0. The farmers obviously prefer to have fields that generate profit rather than fields with losses.

The king wants to give to one farmer the L fields that are closer to his farm, starting from one end of the road, and the other farmer the R fields that are closer to his farm, starting from the other end of the road. Of course, the values of L and R must be non-negative and such that L+R ~\le~ N. The king wants to be fair to both farmers, so the sum of ~\mathbf{x_i} ~ for the L fields he gives to one farmer should be equal to the sum of ~\mathbf{x_i} ~ for the R fields he gives to the other farmer. He also wants to leave as few fields unused as possible.

What is the minimum possible value of N-(L+R) that can be achieved?

Problem:

Develop a program in one of the IOI languages (PASCAL, C, C++, Java) that reads the value of N and the sequence of numbers ~\mathbf{x_i} ~ and prints the answer to the above question.

Input Files:

The input file named landfight.in is a text file with the following structure. The first line contains an integer N: the number of fields. The next line contains N integers ~\mathbf{x_i} ~, separated in pairs by a space: the economic data of the fields.

Output Files:

The output file named landfight.out is a text file that contains a single line with an integer: the answer to the above question.

Examples of Input - Output Files:

1o

STDIN (landfight.in)

7
3 2 5 7 1 6 4

STDOUT (landfight.out)

2

Explanation: We can give L=3 fields to the left landowner, with a sum of 3+2+5=10, and R=2 fields to the right landowner, again with a sum of 6+4=10. This way, there are two unused fields.

2o

STDIN (landfight.in)

10
5 -2 3 -7 -4 -1 3 -5 6 0

STDOUT (landfight.out)

0

Explanation: We can give L=4 fields to the left landowner, with a sum of 5-2+3-7=-1, and R=6 fields to the right landowner, again with a sum of -4-1+3-5+6+0=-1. This way, there are no unused fields.

3o

STDIN (landfight.in)

5
1 2 3 4 5

STDOUT (landfight.out)

5

Explanation: There is no way to give L fields to one landowner and R fields to the other in such a way that the sums of ~\mathbf{x_i}~ are equal. Therefore, all 5 fields will remain unused.

Constraints:

• 1 ~\le~ Ν ~\le~ 1.000.000
• The sum of the absolute values of all ~\mathbf{x_i}~ will not exceed ~10^9~.
• For test cases with a total value of 20%, 1 ~\le~ Ν ~\le~ 1000.
• For test cases with a total value of 50%, 1 ~\le~ Ν ~\le~ 30.000.
• For test cases with a total value of 70%, ~\mathbf{x_i}~ > 0.

Attention! Be sure to read the input and print the output efficiently, especially if you are programming in C++ or Java.

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 1sec.
Maximum available memory: 64MB.
Headers in the source code: At the beginning of your source code, you should use the following headers.

(* USER: username
LANG: PASCAL
TASK: landfight *)

for PASCAL coders

/* USER: username
LANG: C
TASK: landfight */

for C coders

/* USER: username
LANG: C++
TASK: landfight */

for C++ coders

/* USER: username
LANG: Java
TASK: landfight */

for Java coders

# USER: username
# LANG: Python
# TASK: landfight

for Python coders