Optimal Point on a Line

题意翻译

给你 $n$ 个点，为数轴上的点。找到一个 $x$，到所有数的距离的和最小。 **【输入格式】** 第一行，一个数 $n$（$1 \le n \le 3 \times 10^5$）。 第二行，$n$ 个数，分别为 $x_1, x_2, \ldots, x_n$（$-10^9 \le x_{i} \le 10^9$）。 **【输出格式】** 输出一个数，为到所有数的距离的和最小的数，如果有多个，则输出最左边的（数轴上）。

题目描述

You are given $ n $ points on a line with their coordinates $ x_{i} $ . Find the point $ x $ so the sum of distances to the given points is minimal.

输入输出格式

输入格式

The first line contains integer $ n $ ( $ 1<=n<=3·10^{5} $ ) — the number of points on the line. The second line contains $ n $ integers $ x_{i} $ ( $ -10^{9}<=x_{i}<=10^{9} $ ) — the coordinates of the given $ n $ points.

输出格式

Print the only integer $ x $ — the position of the optimal point on the line. If there are several optimal points print the position of the leftmost one. It is guaranteed that the answer is always the integer.

输入输出样例

输入样例 #1

4
1 2 3 4

输出样例 #1

2