题目描述

小镇上共有 $n$ 所住户，坐标分别为 $a_1,a_2,...,a_n$。镇长想要在某个整数坐标点挖一口井，使得每所住户到水井的距离之和最小。请你找出满足条件的水井坐标。若有多个答案，输出其中的最小值。

输入格式

第一行：一个整数 $n$，表示住所数量。

第二行：$n$ 个整数 $a_1,a_2,...,a_n$，分别表示每所住户的坐标。

输出格式

一个整数，表示水井坐标的最小值。

样例

3
1 2 4

2

数据规模与约束

对于 $60\%$ 的数据，$1≤n≤100，1≤a_i≤100$。

对于 $100\%$ 的数据，$1≤n≤10^5，1≤a_i≤10^9，a_1<a_2<...<a_n$。