공원

어느 국립공원에는 공원 전체를 서쪽에서 동쪽으로 가로지르는, 길지만 폭은 넓지 않은 산맥이 있다. 해마다 수많은 관광객이 이곳을 찾는데, 길을 잘 찾지 못하는 사람이 많다. 그래서 공원 관리소는 산맥 전체를 같은 길이의 구간으로 나눈 지도를 만들기로 했다. 각 분할 지점마다 그 지점의 높이와 함께 다른 두 수를 적으려 하는데, 하나는 그 지점보다 서쪽에 있는 가장 높은 분할 지점의 높이이고, 다른 하나는 동쪽에 있는 가장 높은 분할 지점의 높이이다.

지도는 거의 완성되었고, 이제 각 분할 지점의 서쪽과 동쪽 방향의 최고 높이만 계산하면 된다. 이 값들을 구하는 프로그램을 작성하여라.

첫째 줄에 산맥의 길이를 나타내는 정수 $n$ ($1 \le n \le 1\,000\,000$) 이 주어진다. 이어지는 $n$개의 줄에는 각 분할 지점의 높이 $w_i$ ($1 \le w_i \le 1\,000\,000\,000$) 가 한 줄에 하나씩, 서쪽에서 동쪽 순서로 주어진다.

서쪽에서 동쪽 순서로 각 분할 지점에 대응하는 정확히 $n$개의 줄을 출력한다. 각 줄에는 두 정수 $a_i$ 와 $b_i$ 를 공백 하나로 구분하여 출력한다. $a_i$ 는 지점 $i$ 보다 서쪽에 있는 가장 높은 분할 지점의 높이이고, $b_i$ 는 동쪽에 있는 가장 높은 분할 지점의 높이이다. 만약 지점 $i$ 보다 서쪽에 $w_i$ 보다 높은 봉우리가 없으면 $a_i = w_i$ 로 한다. 마찬가지로 지점 $i$ 보다 동쪽에 $w_i$ 보다 높은 봉우리가 없으면 $b_i = w_i$ 로 한다.