Beadman

Interview

Time limit1sMemory limit1024 MB

Summary

Given counts of N bead types, repeatedly remove one bead of each of two different types; find the minimum number of beads that can remain.

Level: Medium4 of 10
Topics: Greedy, Math, Sorting, Implementation
Solved: No attempts yet

Problem

There is a man called Beadman who loves beads very much. Beadman wants every bead he sees, and today he has found a bead he wants. However, Beadman already has so many beads that he has reached the point where he can no longer keep any more.

Beadman knows that when two beads of different types collide, both break and disappear. Using this fact, Beadman wants to make the number of beads he currently has as small as possible. But the number of beads is so large that Beadman simply could not work it out.

You, a street problem-solver, find Beadman worrying on the street and hear from him why he is worried. Since you have met by chance, you decide to solve Beadman's problem. When two beads of different types are collided so as to remove as many beads as possible, find the number of beads that remain.

Input

The first line gives N, the number of types of beads Beadman has. (1 ≤ N ≤ 105)

The next N lines give x1, x2, x3, ..., xN. xi is the number of beads of the i-th type that Beadman has. (1 ≤ x**i ≤ 109)

Output

Print the number of beads that remain when Beadman removes as many beads as possible.

Examples3

Example 1
Input
```
1
1000000000
```
Expected output
```
1000000000
```
Example 2
Input
```
2
100
50
```
Expected output
```
50
```
Example 3
Input
```
3
2
2
4
```
Expected output
```
0
```