Park

A national park is famous for a long (though not very wide) mountain range that stretches across the whole park from west to east. Every year crowds of tourists visit, and many of them are not very good at finding their way. So the park management decided to prepare a map of the entire range, divided into segments of equal length. At each division point the management wants to record the height of that point together with two other numbers: the height of the highest division point to the west of it, and the height of the highest division point to the east of it.

The map is almost ready. All that remains is to compute the maximum heights to the west and to the east of each division point. The park management asks you to write a program that determines these values.

The first line of standard input contains one integer $n$ ($1 \le n \le 1\,000\,000$), the length of the mountain range. Each of the next $n$ lines contains one integer $w_i$ ($1 \le w_i \le 1\,000\,000\,000$), the height of the $i$-th division point. The points are given in order from west to east.

Your program should print exactly $n$ lines to standard output, corresponding to the successive division points (in order from west to east). Each of these lines should contain two integers $a_i$ and $b_i$ separated by a single space: the height of the highest division point to the west of point $i$, and the height of the highest division point to the east of it. If there is no peak higher than $w_i$ to the west of point $i$, take $a_i = w_i$. Likewise, if there is no peak higher than $w_i$ to the east of point $i$, take $b_i = w_i$.