Optimal Gathering Location

After 25 years since graduation, our protagonist is preparing a class reunion. After countless phone calls, he finally gathered all his classmates' addresses. Although a few remain in the same city, most live in other cities. Interestingly, all the addresses lie on a single railway line. He now needs to choose a location for the reunion such that the total travel cost for everyone is minimized. In mathematical terms, given cities with coordinates \(x_1, x_2, \ldots, x_n\) (with Moscow at coordinate 0), you need to choose one city \(x\) (from the given list) that minimizes

[ \sum_{i=1}^{n} |x_i - x| ]

If there is a tie (i.e. several cities yield the same total cost), choose the city that is closest to Moscow (i.e. with the smallest \(|x|\)).

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), representing the number of addresses. The second line contains \(n\) integers, representing the coordinates of the cities located on the railway line. It is guaranteed that all coordinates are integers. Moscow is assumed to be at coordinate 0.

outputFormat

Output a single integer: the coordinate of the chosen city that minimizes the total travel cost. In case of ties, output the coordinate that is closest to Moscow (i.e. has the smallest absolute value).

sample

5
-5 -2 1 3 10

1