Home => ProblemSet => [AGC006D] Median Pyramid Hard
2320: [AGC006D] Median Pyramid Hard
Time Limit: 1 Sec Memory Limit: 128 MB Submit: 0 Solved: 4[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]
Description
有一个 N 层的金字塔。每一层自上而下编号为 1,2,…,N。对于每个 1≤i≤N，第 i 层有 2i−1 个方块横向排列。此外，每一层中央的方块纵向排列在一条直线上。
N=4 层的金字塔
Sunuque 君在第 N 层的方块上写下了 1,2,…,2N−1 的一个排列（即一个顺列）。接着，他按照如下规则，为剩下的所有方块填写整数：
方块填写整数的例子
之后，Sunuque 君把所有方块上的整数都擦掉了。他只记得第 N 层方块上写的顺列为 (a1,a2,…,a2N−1)。
请你求出第 1 层方块上填写的整数。
N=4 层的金字塔 Sunuque 君在第 N 层的方块上写下了 1,2,…,2N−1 的一个排列（即一个顺列）。接着，他按照如下规则，为剩下的所有方块填写整数：
- 某个方块上填写的整数，是其左下、正下、右下三个方块上所写整数的中位数。
方块填写整数的例子 之后，Sunuque 君把所有方块上的整数都擦掉了。他只记得第 N 层方块上写的顺列为 (a1,a2,…,a2N−1)。
请你求出第 1 层方块上填写的整数。
Input
输入通过标准输入给出，格式如下：
N
a1 a2 … a2N−1
N
a1 a2 … a2N−1
Output
请输出第 1 层方块上填写的整数。
Sample Input Copy
4
1 6 3 7 4 5 2
Sample Output Copy
4
HINT
- 2≤N≤105
- (a1,a2,…,a2N−1) 是 1,2,…,2N−1 的一个排列。