Optimal Warehouse Location

You are given a number line with N stores located at positions \(A_1, A_2, \dots, A_N\). A warehouse is to be built on the number line, and every morning a truck delivers goods from the warehouse to each store.

To maximize efficiency, determine the position to build the warehouse so that the total distance traveled from the warehouse to all the stores is minimized.

Recall that the total distance is given by:

\[ D(x) = \sum_{i=1}^N |A_i - x| \]

It is well-known that the function \(D(x)\) is minimized when \(x\) is the median of \(A_1, A_2, \dots, A_N\). If N is even, you may output the lower median.

inputFormat

The first line contains an integer N representing the number of stores.

The second line contains N space-separated integers \(A_1, A_2, \dots, A_N\) representing the positions of the stores on the number line.

outputFormat

Output a single integer representing the optimal position at which to build the warehouse to minimize the total distance.

sample

3
1 2 3

2