← 返回题目列表

Codeforces · 710/B

B. 线上的最佳点

中文机器翻译题面 查看原题

给定一条线上的 n 个点,其坐标为 xi。找到点 x ,使到给定点的距离之和最小。

输入

第一行包含整数 n (1 ≤ n ≤ 3·105) — 线上的点数。

第二行包含 n 个整数 xi ( - 109 ≤ xi ≤ 109) — 给定 n 个点的坐标。

输出

打印唯一的整数 x — 直线上最佳点的位置。如果有多个最佳点,则打印最左边一个的位置。保证答案始终是整数。

示例

输入 #1

4
1 2 3 4

输出 #1

2