역 LIS

친구 Gunilla는 인터넷 감시가 점점 심해지는 것에 불만을 느끼고 있다. Gunilla는 널리 쓰이는 암호화 프로토콜에 백도어를 추가하자는 제안을 몹시 싫어한다. 이에 맞서기 위해 Gunilla는 자신만의 암호 체계를 만들기로 했다.

Gunilla의 알고리즘은 먼저 길이가 $N$인 순열을 선택하며 시작하고, 이 순열을 $\pi$라고 부른다. 순열은 $1$부터 $N$까지의 수가 각각 정확히 한 번씩 등장하도록 어떤 순서로 나열한 목록이다. 순열 $\pi$는 Gunilla의 비밀 키로, 이것이 공개되면 Gunilla의 메시지를 복호화할 수 있다. 프로토콜을 강력하게 유지하기 위해 Gunilla는 프로토콜이 정확히 어떻게 작동하는지 공개하지 않았다. 하지만 이 암호 체계의 핵심에는 함수 LIS의 역을 구하기 어렵다는 가정이 있음을 알아냈다. LIS은 다음 Python 코드로 계산할 수 있다.

def LIS(pi):
  N=len(pi)
  lis = []
  for i in range(N):
    lis_ending_at_i = 0
    for j in range(i):
      if pi[i] > pi[j]:
        lis_ending_at_i = max(lis_ending_at_i, lis[j])
    lis.append(lis_ending_at_i + 1)
  return lis

수학적 표기법으로, $L(\pi)_i$를 마지막 원소가 $\pi_i$인 $\pi$의 최장 증가 부분 수열(https://en.wikipedia.org/wiki/Longest_increasing_subsequence)의 길이라고 하자. 그러면,

$\texttt{LIS}(\pi)=[L(\pi)_1, L(\pi)_2, \dots, L(\pi)_N]$

Gunilla는 LIS의 역을 쉽게 구할 수 없다고 가정하므로(어쨌든 가능한 $\pi$가 $N!$개 있다), $\texttt{LIS}(\pi)$은 기꺼이 주지만 $\pi$은 주지 않는다. Gunilla가 취약한 암호 체계를 사용하지 못하게 하려면 그 취약성을 증명해야 한다. $\texttt{LIS}(\pi)$의 출력이 주어질 때, 유효한 $\pi$를 아무거나 찾아라.

채점

여러 테스트 그룹으로 해답을 검사한다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제약 조건

$1$ |$5$| $N \leq 8$

$2$ |$25$| $L(\pi)_i \leq 2$

$3$ |$25$| $N \leq 1000$

$4$ |$25$| $\pi$는 균등 무작위로 생성되었다(균등 무작위란 길이가 $N$인 모든 순열이 선택될 가능성이 같도록 순열을 추출했다는 뜻이다.).

$5$ |$20$| 추가 제약 조건 없음.

입력의 첫 번째 줄에는 순열의 길이를 나타내는 정수 $N$이 주어진다($1 \leq N \leq 2 \cdot 10^5$).

다음 줄에는 정수 $L(\pi)_1, L(\pi)_2, \dots, L(\pi)_N$이 주어진다($1 \leq L(\pi)_i \leq N$). 이 수열이 $\texttt{LIS}(\pi)$의 값이 되는 $\pi$가 적어도 하나 존재함이 보장된다.

유효한 $\pi$ 중 하나에 대해 공백으로 구분된 정수 $N$개, 즉 $\pi_1, \pi_2, \dots, \pi_N$을 출력한다. 유효한 $\pi$가 적어도 하나 존재함이 보장된다.