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 翻译