题目描述

Byteotia 的社会结构可以看作一座共有 $n$ 层的金字塔。各层自上而下编号为 $1,2,\ldots,n$。

第 $k$ 层共有 $2k-1$ 个位置。

最底层，也就是第 $n$ 层的每个位置已经给定一个整数值。上面的每一层都由其下一层构造得到。

具体来说，假设某一层当前从左到右的数为

$a_1,a_2,\ldots,a_{2d+1}$，

那么它正上方一层的 $2d-1$ 个数依次为

$\operatorname{med}(a_1,a_2,a_3),\operatorname{med}(a_2,a_3,a_4),\ldots,\operatorname{med}(a_{2d-1},a_{2d},a_{2d+1})$，

其中 $\operatorname{med}(x,y,z)$ 表示三个数的中位数。

不断执行这一过程，最终第 $1$ 层只剩下一个数。

你的任务是求出金字塔顶端这个数的值。

输入格式

第一行包含一个整数 $n$，表示金字塔的层数：

$2\le n\le100000$。

第二行包含 $2n-1$ 个整数 $a_i$，表示最底层从左到右的初始数值：

$-10^9\le a_i\le10^9$。

输出格式

输出一个整数，表示最终位于金字塔顶端的数值。

子任务

样例

5
5 3 6 1 2 9 7 8 4

2

说明

对于样例，最底层为：

5 3 6 1 2 9 7 8 4

第一轮取连续三个数的中位数后得到：

5 3 2 2 7 8 7

继续按照同样的规则逐层缩短，最终顶端的值为 $2$。