Description

        数学中，我们经常这么来定义中位数：有 n 个数，从小到大排序以后，排名中间的数就是中位数，当 n 是奇数的时候，中位数只有 1 个，当 n 是偶数的时候，中间
两个数都是中位数。注意，我们这里用到都是 3 个数的中位数。比如，有 3 个数 1、3、4，那么中位数就是 3，如果有 3 个数 3、2、2，那么中位数就是 2。
        我们有一个神奇的三角形，这个三角形的第 1 行只有 1 个数，第 2 行有 3 个数，第 n 行有 2n − 1 个数。下图就是一个简单的例子：

        这里的第 3 行（也就是最后一行）是提前给定的，剩余的数都是按照规则产生的。第 i 行第 j 列的数是第 i + 1 行第 j − 1 列和第 i + 1 行第 j 列和第 i + 1 行第j + 1 这 3 个数的中位数。这里第 2 行第 2 列的 1 是 1、1、2 的中位数，第 2 行第 3列的 2 是 1、2、4 的中位数，第 2 行第 4 列的数是 2、4、1 的中位数，第 1 行第 3列的数是 1、2、2 的中位数。

        现在我们的问题是告诉你总共有 n 行，以及最后一行的 2n − 1 个数，请你算出第 1 行第 n 列上的那个数是多少。

Input Format

middle.in 输入的第一行是一个正整数 n，表示这个三角形的层数。
接下来一行有 2n − 1 个整数 a i ，表示最后一行上的整数，中间用一个空格隔开。

Output Format

middle.out 输出第 1 行第 n 列上的数，也就是第 1 行唯一的那个数。

3
2 3 2 5 1

2

Hint

【输入样例 1】
3
2 3 2 5 1
【输出样例 1】
2
【输入样例 2】
5
4 3 3 6 7 4 6 3 7
【输出样例 2】
6
【输入样例 3】
10
5 8 1 1 7 6 6 5 8 6 2 9 9 5 9 4 2 9 3
【输出样例 2】
6
【数据范围】
对于所有的数据 1 ≤ n ≤ 10^{^5}，1 ≤ a i ≤ 10^{^9}。

Source

二分答案