Optimal Teleportation Position

You are given the coordinates of n houses on a straight line. Your task is to determine the optimal position to install a teleportation device in order to minimize the total travel distance. The optimal position is the median of the house coordinates. In case of an even number of houses, the left median (i.e. the element at index \(rac{n-1}{2}\)) is chosen.

Note on median: Given a sorted list of houses \(a_0 \le a_1 \le ... \le a_{n-1}\), the answer is \(a_{\lfloor\frac{n-1}{2}\rfloor}\). This minimizes the overall distance.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

• The first line contains an integer n, representing the number of houses.
• The second line contains n space-separated integers representing the coordinates of the houses.

outputFormat

Output a single integer to standard output (stdout): the coordinate of the optimal position to install the teleportation device.

5
2 3 7 8 12

7