Optimal Meeting Point

You are given a sorted list of n integer points on a number line. Your task is to compute the optimal meeting point that minimizes the total travel distance for all individuals. Mathematically, the goal is to minimize the sum

where x is the meeting point and \(a_1, a_2, \dots, a_n\) are the positions of the people on the number line. It is known that any median of the list minimizes the sum of absolute differences. In this problem, if there are an even number of points, choose the lower median (i.e. the \(\left(\frac{n}{2}\right)\)th element in 1-indexed order).

Note: The input list is provided in non-decreasing order.

inputFormat

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

• The first line contains a single integer n representing the number of points.
• The second line contains n space-separated integers representing the positions on the number line.

outputFormat

Output the optimal meeting point to stdout as a single integer.

1
3

3