题目描述

数学中，我们经常这么来定义中位数：有 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 列上的那个数是多少。

输入格式

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

输出格式

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

3
2 3 2 5 1

2

5
4 3 3 6 7 4 6 3 7

6

10
5 8 1 1 7 6 6 5 8 6 2 9 9 5 9 4 2 9 3

6

数据规模

对于所有的数据 $1≤n≤10^5$，$1≤a_​i​≤10^9$。