AT_agc006_d [AGC006D] Median Pyramid Hard

有一个 $N$ 层的金字塔。每一层自上而下编号为 $1, 2, \ldots, N$。对于每个 $1 \leq i \leq N$，第 $i$ 层有 $2i-1$ 个方块横向排列。此外，每一层中央的方块纵向排列在一条直线上。  $N=4$ 层的金字塔 Sunuque 君在第 $N$ 层的方块上写下了 $1, 2, \ldots, 2N-1$ 的一个排列（即一个顺列）。接着，他按照如下规则，为剩下的所有方块填写整数： - 某个方块上填写的整数，是其左下、正下、右下三个方块上所写整数的中位数。  方块填写整数的例子 之后，Sunuque 君把所有方块上的整数都擦掉了。他只记得第 $N$ 层方块上写的顺列为 $(a_1, a_2, \ldots, a_{2N-1})$。 请你求出第 $1$ 层方块上填写的整数。

输入通过标准输入给出，格式如下： > $N$ $a_1$ $a_2$ $\ldots$ $a_{2N-1}$

请输出第 $1$ 层方块上填写的整数。

## 限制 - $2 \leq N \leq 10^5$ - $(a_1, a_2, \ldots, a_{2N-1})$ 是 $1, 2, \ldots, 2N-1$ 的一个排列。 ## 样例说明 1 这是题目描述中的图示例。 由 ChatGPT 4.1 翻译