Commuting Functions

Two functions $f$ and $g$ ($f, g : X \to X$) commute if and only if $f(g(x)) = g(f(x))$ for every $x \in X$. For example, $f(x) = x + 1$ and $g(x) = x - 2$ commute, whereas $f(x) = x + 1$ and $g(x) = 2x$ do not.

Every function $h$ ($h : N_n \to N_n$, where $N_n = \{1, 2, \ldots, n\}$ and $n$ is a positive integer) can be written as a value list — a list whose $i$-th element equals $h(i)$. For example, the function $h(x) = \lceil x/2 \rceil$ from $N_5$ to $N_5$ has the value list $[1, 1, 2, 2, 3]$.

Value lists are ordered lexicographically: the list $[a_1 \ldots a_n]$ is smaller than the list $[b_1 \ldots b_n]$ if and only if there is an index $k$ with $a_k < b_k$ and $a_l = b_l$ for every index $l < k$.

A function $f$ ($f : X \to X$) is bijective if for every $y \in X$ there is exactly one $x \in X$ with $f(x) = y$.

Given a bijective function $f$ ($f : N_n \to N_n$), find the function $g$ that commutes with $f$ and has the lexicographically smallest possible value list.

The first line contains a single integer $n$ — the number of elements in the value list of the bijective function $f$ ($1 \le n \le 200\,000$).

The second line contains the value list of $f$: $n$ integers that form a permutation of $1, 2, \ldots, n$.

Print a single line with $n$ integers — the value list of the function $g$ that commutes with $f$ and has the lexicographically smallest value list.