가환 함수

두 함수 $f$와 $g$ ($f, g : X \to X$)가 가환이라는 것은 모든 $x \in X$에 대해 $f(g(x)) = g(f(x))$가 성립한다는 뜻이다. 예를 들어 $f(x) = x + 1$과 $g(x) = x - 2$는 가환이지만, $f(x) = x + 1$과 $g(x) = 2x$는 가환이 아니다.

모든 함수 $h$ ($h : N_n \to N_n$, 여기서 $N_n = {1, 2, \ldots, n}$이고 $n$은 양의 정수)는 값 목록으로 나타낼 수 있다. 값 목록이란 $i$번째 원소가 $h(i)$와 같은 목록이다. 예를 들어 $N_5$에서 $N_5$로 가는 함수 $h(x) = \lceil x/2 \rceil$의 값 목록은 $[1, 1, 2, 2, 3]$이다.

값 목록은 사전순으로 비교한다. 목록 $[a_1 \ldots a_n]$이 목록 $[b_1 \ldots b_n]$보다 작다는 것은, 어떤 인덱스 $k$가 존재하여 $a_k < b_k$이고 모든 인덱스 $l < k$에 대해 $a_l = b_l$인 경우를 말한다.

함수 $f$ ($f : X \to X$)가 전단사라는 것은 모든 $y \in X$에 대해 $f(x) = y$를 만족하는 $x \in X$가 정확히 하나 존재한다는 뜻이다.

전단사 함수 $f$ ($f : N_n \to N_n$)가 주어질 때, $f$와 가환이면서 값 목록이 사전순으로 가장 작은 함수 $g$를 구하여라.

첫째 줄에 전단사 함수 $f$의 값 목록에 들어 있는 원소의 개수를 나타내는 정수 $n$이 주어진다 ($1 \le n \le 200,000$).

둘째 줄에 $f$의 값 목록이 주어진다. 이는 $1, 2, \ldots, n$의 순열을 이루는 $n$개의 정수이다.

$f$와 가환이면서 값 목록이 사전순으로 가장 작은 함수 $g$의 값 목록을, $n$개의 정수로 한 줄에 출력한다.