다음 3-1-2 패턴 회피 순열

순열의 패턴 회피는 조합론과 컴퓨터과학에서 오래 연구된 주제다. 자연수 $1, \dots, n$의 순열 $p_1, p_2, \dots, p_n$이 3-1-2 패턴을 회피한다는 것은 $p_i > p_j$, $p_i > p_k$, $p_j < p_k$를 동시에 만족하는 첨자 $1 \le i < j < k \le n$이 없다는 뜻이다.

3-1-2 패턴을 회피하는 $1, \dots, n$의 순열을 모두 사전순으로 나열하자. 이 목록에서 주어진 순열 바로 다음에 오는 순열을 구하라. 감소 수열 $n, n-1, \dots, 1$이 목록의 마지막 항목이고 입력은 이 순열이 아니므로 답은 항상 존재한다.

첫째 줄에 정수 $n$ ($3 \le n \le 10000$)이 주어진다. 둘째 줄에 $1, \dots, n$의 순열이 공백 하나로 구분된 $n$개의 정수로 주어진다. 이 순열은 3-1-2 패턴을 회피하며, 감소 수열 $n, n-1, \dots, 1$은 아니다.

첫째 줄에 3-1-2 패턴을 회피하는 순열 중 입력 순열의 사전순 바로 다음 순열을 출력한다. 수는 공백 하나로 구분한다.