Pulling Their Weight

Interview

Time limit1sMemory limit1024 MB

Summary

Find the smallest integer threshold t that splits the animal weights into two groups of equal total weight, with ties at t handled by pairing.

Level: Medium5 of 10
Topics: Sorting, Prefix sum, Binary search, Array
Solved: No attempts yet

Problem

To save money, Santa Claus has started hiring animals besides reindeer to pull his sleigh through short-term 'gig' contracts. As a result, the animals that actually show up to pull the sleigh on any given trip can vary greatly in size.

Last week he had $2$ buffalo, $37$ voles and a schnauzer. Unfortunately, both buffalo were hitched on the left side and the entire sleigh flipped over in mid-flight due to the weight imbalance.

To prevent such accidents in the future, Santa needs to divide the animals for a given trip into two groups such that the sum of the weights of all animals in one group equals the sum of the weights of all animals in the other. To make the hitching process efficient, Santa is looking for an integer target weight $t$ such that all animals lighter than $t$ go in one group and those heavier than $t$ go in the other. If there are multiple such $t$ , he wants the smallest one. There is one small wrinkle: what should be done if some animals have weight exactly equal to $t$ ? Santa solves the problem this way: if there are an even number of such animals, he divides them equally between the two groups (thus distributing the weight evenly). But if there are an odd number of such animals, then one of those animals is sent to work with the elves making toys (it is put in neither group), and the remaining (now even) number are divided evenly between the two groups.

Input

Input describes a list of animals' weights. The first line contains an integer $m$ ( $2 \le m \le 10^5$ ), the number of animals. The next $m$ lines each contain one positive integer. These are the weights of the animals in ounces. Animals weighing more than $20\,000$ ounces are too big to pull the sleigh, so no given weight exceeds this maximum.

Output

Output the smallest integer target weight $t$ , as described above. It is guaranteed that such an integer can be found.

Examples3

Example 1
Input
```
4
3
6
1
2
```
Expected output
```
4
```
Example 2
Input
```
4
11
8
3
10
```
Expected output
```
10
```
Example 3
Input
```
2
99
99
```
Expected output
```
99
```