100 atcoder#AGC006D. [AGC006D] Median Pyramid Hard

[AGC006D] Median Pyramid Hard

题目描述

N N 段のピラミッドがあります。 段は上から順に 1 1 , 2 2 , ... ... , N N と番号が振られています。 各 1 < =i < =N 1\ <\ =i\ <\ =N について、i i 段目には 2i1 2i-1 個のブロックが横一列に並んでいます。 また、各段の中央のブロックに注目すると、これらは縦一列に並んでいます。

N=4 N=4 段のピラミッド

すぬけ君は N N 段目のブロックに (1 1 , 2 2 , ... ... , 2N1 2N-1 ) を並べ替えたもの(順列)を書き込みました。 さらに、次のルールに従い、残りすべてのブロックに整数を書き込みました。

  • あるブロックに書き込まれる整数は、そのブロックの左下、真下、右下のブロックに書き込まれた整数の中央値である。

ブロックに整数を書き込む例

その後、すぬけ君はすべてのブロックに書き込まれた整数を消してしまいました。 すぬけ君は、N N 段目のブロックに書き込まれた順列が (a1 a_1 , a2 a_2 , ... ... , a2N1 a_{2N-1} ) であったことだけを覚えています。

1 1 段目のブロックに書き込まれた整数を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

N N a1 a_1 a2 a_2 ... ... a2N1 a_{2N-1}

输出格式

1 1 段目のブロックに書き込まれた整数を出力せよ。

题目大意

给出一个 NN 层的方格金字塔,自顶向下依次标号为第 11 到第 NN 层。
其中第 i(1iN)i(1 \le i \le N) 层有 2i12i - 1 个方格。(具体形态见下面的图)
NN 层有一个 112N12N-1 的排列,其他层的数字按以下规则生成:方格 bb 中填写的整数,是方格 bb 正下方、左下方和右下方方格中所写整数的中位数。
现在给出第 NN 层的数字,请你求第一层的数字。

翻译提供者:WAAutoMaton

4
1 6 3 7 4 5 2
4
2
1 2 3
2

提示

制約

  • 2 < =N < =105 2\ <\ =N\ <\ =10^5
  • (a1 a_1 , a2 a_2 , ... ... , a2N1 a_{2N-1} ) は (1 1 , 2 2 , ... ... , 2N1 2N-1 ) の順列である。

Sample Explanation 1

問題文中の図の例です。