该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有 $n$ 只蚂蚁分布在数轴上，第 $i$ 只蚂蚁初始位置为 $x_i$（保证 $x_i$ 为奇数）。

任意时刻，每只蚂蚁会选择一只与自己不在同一位置且距离最近的蚂蚁作为目标并朝它移动；若满足最近距离的蚂蚁不止一只，则选择其中位置最靠左的一只。

所有蚂蚁速度相同。

当两只（或多只）蚂蚁相遇后，会立即再次按上述规则重新选择目标并继续运动，直到所有蚂蚁最终相遇到同一个位置。

可以证明，所有蚂蚁一定会相遇。请你求出最终相遇位置。

输入

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数 $x_1, x_2, \ldots, x_n$。

输出

输出一个整数，表示最终相遇位置。

样例

样例输入 1

3
1 5 9

样例输出 1

5

样例输入 2

4
-7 -1 3 11

样例输出 2

2

样例解释

• 样例 1 中，最终相遇位置为最左与最右初始位置中点：$(1+9)/2=5$。
• 样例 2 中，最左位置为 $-7$，最右位置为 $11$，最终相遇位置为 $(-7+11)/2=2$。

数据范围

保证： $n \geq 2$，且所有 $x_i$ 均为奇数。