Government Help

Two major banks in our country are in serious trouble. We will call them Bank A and Bank B — we cannot reveal their real names, as it might ruin them.

To rescue the banks, the government has prepared several financial support packages to be shared between the two banks. There is one important condition: the packages are handed out one at a time, and at every moment during this process the difference between the total amounts received by the two banks must be kept as small as possible. Otherwise one bank would gain a large advantage over the other.

You may choose the order in which the packages are handed out and which bank each package goes to. If, at some moment, we call the absolute difference between the totals received by the two banks the "difference" at that moment, the goal is to minimize the largest difference that occurs during the whole process.

For example, suppose there are four packages worth 100000, 110000, 120000, and 150000. Some ways of distributing them make the largest difference grow to 130000, but a better way keeps the largest difference down to 100000. Hence the answer for this case is 100000.

The input contains several groups of packages. Each group begins with a line containing a single positive integer $N$, the number of packages ($1 \le N \le 50000$). The next line contains $N$ space-separated positive integers, each between 100000 and 199999 inclusive; these are the amounts of money in the individual packages. The packages may be handed out in any order, so the order of the numbers on the second line does not matter.

The last group is followed by a line containing a single 0.

For each group of packages, print on its own line the minimum possible value of the largest difference that occurs during the whole distribution.

In other words, choose the order of the packages and the bank each one goes to so that the largest of the moment-by-moment differences (the absolute difference between the totals held by the two banks) is as small as possible, and print that minimized largest difference as an integer.