방탈출

시간 제한1초메모리 제한64 MB

요약

각 위치에서 시작하는 가장 긴 증가 부분 수열의 길이가 주어질 때, 이를 만족하는 가장 사전순으로 작은 순열을 구한다.

난이도: 보통10점 중 7점
유형: 그리디, 세그먼트 트리, 이분 탐색
정답자: 아직 제출이 없습니다

문제

방탈출 카페의 어느 방에는 이런 퀴즈가 있다. 자물쇠의 비밀번호는 길이가 $N$ 인 순열이다. 길이가 $N$ 인 순열은 서로 다른 양의 정수 $N$ 개로 이루어진 수열이고, 각 원소는 $N$ 이하이다.

힌트로 수열 $A$ 가 주어진다. 위치 $i$ 에서 시작하는 가장 긴 증가 부분 수열의 길이가 $A_i$ 이다. 즉, 위치 $i$ 를 첫 원소로 삼아 인덱스가 커지는 순서로 값도 커지도록 고른 부분 수열 중 가장 긴 것의 길이가 $A_i$ 이다.

조건을 만족하는 순열이 여럿일 수 있으므로 그중 사전순으로 가장 앞서는 것을 구한다. 순열 $P$ 가 순열 $Q$ 보다 사전순으로 앞선다는 것은, $P_i < Q_i$ 이면서 $j < i$ 인 모든 $j$ 에 대해 $P_j = Q_j$ 인 인덱스 $i$ 가 있다는 뜻이다. 조건을 만족하는 순열은 적어도 하나 존재한다.

입력

첫째 줄에 정수 $N$ ( $1 \le N \le 10^5$ )이 주어진다.

둘째 줄에 정수 $A_1, A_2, \dots, A_N$ ( $1 \le A_i \le N$ )이 공백으로 구분되어 주어진다.

조건을 만족하는 순열이 적어도 하나 존재함이 보장된다.

출력

조건을 모두 만족하는 순열 중 사전순으로 가장 앞서는 것을 한 줄에 출력한다. 원소는 공백으로 구분한다.

예제2

예제 1
입력
```
4
1 2 2 1
```
예상 출력
```
4 2 1 3
```
예제 2
입력
```
1
1
```
예상 출력
```
1
```