상승장 (Hossa)

$n$개의 서로 다른 자연수로 이루어진 수열 $a_1, a_2, \ldots, a_n$을 생각하자. 이 수열이 상승장(hossa)이라는 것은, $i < j < k$를 만족하는 모든 세 위치 $i, j, k$에 대해 다음이 성립한다는 뜻이다: 만약 $a_i < a_j$이면 $a_k > a_i$이다.

직관적으로 말하면, 어떤 두 시점 $i$와 $j$ 사이에 값이 $a_i$에서 $a_j$로 올랐다면($a_i < a_j$), 그 이후의 어떤 날에도 값이 다시 $a_i$ 이하로 떨어지지 않는다는 뜻이다.

예를 들어 원소가 $1, 2, 3, 4$인 상승장은 모두 14개이며 다음과 같다.

$(1,2,3,4),\ (2,1,3,4),\ (1,3,2,4),\ (3,1,2,4),\ (3,2,1,4),\ (1,2,4,3),\ (2,1,4,3),\ (1,4,2,3),\ (1,4,3,2),\ (4,1,2,3),\ (4,2,1,3),\ (4,1,3,2),\ (4,3,1,2),\ (4,3,2,1)$

반면 $(3,2,4,1)$은 상승장이 아니다. 값이 $3$에서 $4$로 올랐다가 나중에 $1$로 떨어지기 때문이다.

모든 상승장은 $L\,m\,P$ 꼴로 나타낼 수 있다. 여기서 $m$은 수열의 최댓값이고, $L$은 $m$의 왼쪽에 있는 원소들, $P$는 $m$의 오른쪽에 있는 원소들이다. 예를 들어 상승장 $(1,2,4,3)$에서는 $m = 4$, $L = (1,2)$, $P = (3)$이다. 이때 $L$과 $P$도 각각 더 적은 개수의 원소로 이루어진 상승장이 된다.

같은 수들로 이루어진(서로가 서로의 순열인) 두 상승장 $H_1 = L_1\,m\,P_1$과 $H_2 = L_2\,m\,P_2$ 사이의 순서 $H_1 < H_2$를 다음과 같이 정의한다.

1. $P_1$의 원소 개수가 $P_2$의 원소 개수보다 적으면 $H_1 < H_2$이다.
2. 두 개수가 같으면, 상승장 $P_1$이 상승장 $P_2$보다 작은지($P_1 < P_2$)로 판단한다.
3. $P_1$과 $P_2$가 완전히 같은 수열이면, $L_1 < L_2$인지로 판단한다.

이 순서로 원소가 $1, 2, 3, 4$인 상승장을 정렬하면 위에 나열한 순서가 된다. 비교의 예는 다음과 같다.

• $(1,2,3,4) < (2,1,3,4)$: 규칙 3에 의해 $(1,2,3) < (2,1,3)$인지 보면 되고, 다시 규칙 3에 의해 $(1,2) < (2,1)$인지 보면 되며, 이는 규칙 1로 성립한다.
• $(1,4,2,3) < (1,4,3,2)$: 규칙 2에 의해 $(2,3) < (3,2)$이다.

상승장 $H$가 주어질 때, $H$의 바로 다음 상승장 $X$를 구하라. 즉 다음 두 조건을 모두 만족하는 $X$이다.

• $H < X$
• $H < H'$인 모든 상승장 $H'$($X$ 제외)에 대해 $X < H'$

입력으로 주어지는 모든 경우에 대해 그러한 $X$가 항상 존재한다고 가정해도 된다. 예를 들어 $(1,2,3,4)$의 바로 다음 상승장은 $(2,1,3,4)$이고, $(2,1,3,4)$의 바로 다음은 $(1,3,2,4)$, 그 다음은 $(3,1,2,4)$이다.

첫째 줄에 정수 $n$이 주어진다 ($2 \le n \le 10^6$). 둘째 줄에는 어떤 상승장 $H$를 이루는 $n$개의 서로 다른 자연수가 공백으로 구분되어 주어진다. 각 값은 $10^6$ 이하이다.

상승장 $H$의 바로 다음 상승장을 이루는 $n$개의 자연수를 공백으로 구분하여 한 줄에 출력한다.