beecrowd | 1601

Partition of The Herd

By Marcio T. I. Oshiro Brazil

Timelimit: 5

The Moroccan cuisine is very famous for its delicious recipes that involve various kinds of roasted meats, but especially sheep, which are created in the region since the eighth century. A curious Berber tradition involves sharing the creation o fga pastor at the time of his death. Regardless of the number of children he has, only the eldest and youngest son are entitled to inheritance. The other children do not gain anything. Then, all animals are weighed, and the weights (rounded to the nearest integer) are considered. The flock is then divided into two parts so that in each of the animals have similar weights. More specifically, the flock is partitioned into two parts, A and B, such that, 

is minimal. So, the firstborn gets the part of the flock of greater weight, and the last child, gets the part of lower weight. This does not seems very fair, but it is the tradition there.

Input

The input consists of several instances and ends with the end of file (EOF). 

The first line of each instance contains an integer N (2 ≤ N ≤ 1000) indicating the number of sheep in the herd. The next line contains N integers separated by a space, corresponding to the weights (0 ≤ weight (·) ≤ 100) of sheep.

Output

For each instance, print on a single line the minimum value of S (A, B).

Sample Input Sample Output

4
1 4 4 1
4
1 2 3 4

0
2