#P12909. [AGC006D] Median Pyramid Hard

    ID: 12093 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-二分答案不变量分析

[AGC006D] Median Pyramid Hard

题目描述

有一个 NN 层的金字塔。每一层自上而下编号为 1,2,…,N1, 2, \ldots, N。对于每个 1≤i≤N1 \leq i \leq N,第 ii 层有 2i−12i-1 个方块横向排列。此外,每一层中央的方块纵向排列在一条直线上。

N=4N=4 层的金字塔

Sunuque 君在第 NN 层的方块上写下了 1,2,…,2N−11, 2, \ldots, 2N-1 的一个排列(即一个顺列)。接着,他按照如下规则,为剩下的所有方块填写整数:

  • 某个方块上填写的整数,是其左下、正下、右下三个方块上所写整数的中位数。

方块填写整数的例子

之后,Sunuque 君把所有方块上的整数都擦掉了。他只记得第 NN 层方块上写的顺列为 (a1,a2,…,a2N−1)(a_1, a_2, \ldots, a_{2N-1})。

请你求出第 11 层方块上填写的整数。

输入格式

输入通过标准输入给出,格式如下:

NN a1a_1 a2a_2 …\ldots a2N−1a_{2N-1}

输出格式

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

输入输出样例 #1

输入 #1

4
1 6 3 7 4 5 2

输出 #1

4

输入输出样例 #2

输入 #2

2
1 2 3

输出 #2

2

说明/提示

限制

  • 2≤N≤1052 \leq N \leq 10^5
  • (a1,a2,…,a2N−1)(a_1, a_2, \ldots, a_{2N-1}) 是 1,2,…,2N−11, 2, \ldots, 2N-1 的一个排列。

样例说明 1

这是题目描述中的图示例。