A72012. 蚂蚁相遇(ant)

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

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

所有蚂蚁速度相同。

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

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

第一行输入一个整数 n。

第二行输入 n 个整数 x_1,x_2,...,x_n。

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

样例解释

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

样例 2 中，最左位置为 -7，最右位置为 11，最终相遇位置为 (-7+11)/2=2。

数据范围

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