atcoder#AGC006D. [AGC006D] Median Pyramid Hard
[AGC006D] Median Pyramid Hard
Score : points
Problem Statement
We have a pyramid with steps, built with blocks. The steps are numbered through from top to bottom. For each , step consists of blocks aligned horizontally. The pyramid is built so that the blocks at the centers of the steps are aligned vertically.
A pyramid with steps
Snuke wrote a permutation of (, , , ) into the blocks of step . Then, he wrote integers into all remaining blocks, under the following rule:
- The integer written into a block must be equal to the median of the three integers written into the three blocks directly under , or to the lower left or lower right of .
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 was (, , , ).
Find the integer written into the block of step .
Constraints
- (, , , ) is a permutation of (, , , ).
Input
The input is given from Standard Input in the following format:
Output
Print the integer written into the block of step .
4
1 6 3 7 4 5 2
4
This case corresponds to the figure in the problem statement.
2
1 2 3
2