Caroling

Two siblings, Red and Green, want to visit houses along a circular road to sing carols. In each house, the children know in advance how much money the residents usually give them. To save time, they decide to distribute the houses: Red will go to some consecutive houses along the circle, and Green will go to the rest, which are obviously also consecutive. To make the distribution fair, they want to divide the houses in such a way that the total amounts of money Red and Green receive differ as little as possible.

Problem:

Develop a program in one of the IOI languages (PASCAL, C, C++, Java) that, after reading the number of houses and the amounts of donations in each house, will find the minimum possible value of the difference between the total amounts of money that Red and Green can receive.

Input Files:

The input files with the name kalanta.in are text files with the following structure: The first line contains an integer N, the number of houses (1 ~\le~ N ~\le~ 1.000.000). The second line contains ~N~ positive integers ~x_i~, separated in pairs by a space. Each number ~\mathbf{x_i}~ (1 ~\le x_i \le~ 1.000) corresponds to the amount of money the children will receive from the ~i~-th house.

Output Files:

The output files with the name kalanta.out are text files with the following structure: They have exactly one line that contains exactly one number: the minimum (absolute) value of the difference between the total amounts of money that the two children can receive.

Examples of Input - Output Files

1ο

STDIN (kalanta.in)

8
7 5 1 3 8 9 11 8

STDOUT (kalanta.out)

0

In this example, Red and Green can distribute the houses in such a way that they receive exactly the same amount of money (i.e., the minimum possible value of the difference is zero). This can be achieved if Red visits the houses from the second (5) to the sixth (9), and Green visits the remaining houses. Then, both children will have received a total of 26 €.

2nd

STDIN (kalanta.in)

9
10 14 75 90 3 5 40 4 8

STDOUT (kalanta.out)

27

In this example, the children cannot distribute the houses in a way that they receive the same total amount of money. The best they can do is what is shown in the above diagram. Red will visit the houses from the fourth (90) to the seventh (40) and will receive a total of ~90 + 3 + 5 + 40 = 138~ €. Green will visit the remaining houses and will receive ~4 + 8 + 10 + 14 + 75 = 111~ €. Their difference is 27 €, and this is the minimum possible difference.

Notes:

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

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

for PASCAL coders

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

for C coders

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

for C++ coders

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

for Java coders

# USER: username
# LANG: Python
# TASK: kalanta

for Python coders