atcoder#AGC006D. [AGC006D] Median Pyramid Hard

[AGC006D] Median Pyramid Hard

Score : 13001300 points

Problem Statement

We have a pyramid with NN steps, built with blocks. The steps are numbered 11 through NN from top to bottom. For each 1iN1 \leq i \leq N, step ii consists of 2i12i-1 blocks aligned horizontally. The pyramid is built so that the blocks at the centers of the steps are aligned vertically.

A pyramid with N=4N=4 steps

Snuke wrote a permutation of (11, 22, ......, 2N12N-1) into the blocks of step NN. Then, he wrote integers into all remaining blocks, under the following rule:

  • The integer written into a block bb must be equal to the median of the three integers written into the three blocks directly under bb, or to the lower left or lower right of bb.

Writing integers into the blocks

Afterwards, he erased all integers written into the blocks. Now, he only remembers that the permutation written into the blocks of step NN was (a1a_1, a2a_2, ......, a2N1a_{2N-1}).

Find the integer written into the block of step 11.

Constraints

  • 2N1052 \leq N \leq 10^5
  • (a1a_1, a2a_2, ......, a2N1a_{2N-1}) is a permutation of (11, 22, ......, 2N12N-1).

Input

The input is given from Standard Input in the following format:

NN

a1a_1 a2a_2 ...... a2N1a_{2N-1}

Output

Print the integer written into the block of step 11.

4
1 6 3 7 4 5 2
4

This case corresponds to the figure in the problem statement.

2
1 2 3
2