모티와 비밀번호

리크는 손자 모티가 얼마나 기지가 뛰어난지 시험해 보기로 했다. 모티가 아끼는 제시카는 비밀번호 자물쇠가 달린 방에 갇혀 있고, 그녀를 구하려면 모티가 리크의 실험을 통과해야 한다.

리크는 모티 앞에 주스 컵 $n$개를 일렬로 놓았다. 각 컵에는 $1$부터 $n$까지의 정수가 적혀 있다. 왼쪽에서 $i$번째 컵에 적힌 수는 $a_i$이다. 모든 수는 서로 다르며, $1$부터 $n$까지의 순열을 이룬다.

모티는 인접한 두 컵을 원하는 만큼 자리 바꿀 수 있다. 손이 떨려서 자리를 바꿀 때마다 두 컵에서 주스가 조금씩 쏟아진다. 리크는 각 컵을 최대 두 번까지만 만지도록 허락했다. 금고의 비밀번호는 이 실험으로 얻을 수 있는 순열 가운데, 왼쪽에서 오른쪽으로 읽었을 때 사전순으로 가장 큰 순열이다.

모티가 비밀번호를 찾아 제시카를 구하도록 도와라.

첫째 줄에 컵의 개수 $n$이 주어진다 ($1 \le n \le 100\,000$).

둘째 줄에는 실험을 시작할 때 컵에 적힌 정수 $a_1, a_2, \ldots, a_n$이 주어진다 ($1 \le a_i \le n$). 모든 $a_i$는 서로 다르다.

비밀번호를 공백으로 구분한 $n$개의 정수로 출력한다.

길이가 $n$인 순열 $a$가 길이가 $n$인 순열 $b$보다 사전순으로 크다는 것은, 모든 $i$ ($1 \le i \le x - 1$)에 대해 $a_i = b_i$이고 $a_x > b_x$인 $x$가 존재한다는 뜻이다.