26199번 - Permutations 다국어

문제

Let $[n]$ denote the set $\{1, 2, \ldots, n\}$. A permutation of order $n$ is a one-to-one mapping from the set $[n]$ to the set $[n]$. For example, let $\pi \colon [7] \to [7]$ be a concrete permutation of order 7ドル$. We usually represent it with a table like this:

$\pi = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 3 & 7 & 4 & 1 & 6 & 5 & 2\end{pmatrix}.$

This means that $\pi(1) = 3,ドル $\pi(2) = 7,ドル $\pi(3) = 4$ etc. Since the top row is always 1ドル\ 2\ 3 \ldots n,ドル we usually omit it and write down the permutation in the one-line notation:

$\pi = 3\ 7\ 4\ 1\ 6\ 5\ 2.$

The cycle notation is also very popular. We start with element 1ドル$ and determine its image $\pi(1) = 3$. Next, we take the element 3ドル$ and determine its image $\pi(3) = 4$. If we keep doing this, we sooner or later arrive back at the element 1ドル$. Indeed, $\pi(4) = 1$. The permutation $\pi$ contains the cycle $(1\ 3\ 4)$. Then we take the smallest number that has not yet appeared in any cycle - in our case it is 2ドル$ - and repeat the process. Eventually, we obtain to the following:

$\pi = (1\ 3\ 4)\ (2\ 7)\ (5\ 6).$

A permutation of order $n$ can also be represented by an inversion table $b_1\ b_2\ b_3 \ldots b_n$ (0ドル \leq b_i \leq n-i$), where $b_i$ is the number of those elements that are greater than $i$ and appear to the left of $i$ in the one-line notation. In our concrete example, the inversion table is:

3ドル\ 5\ 0\ 1\ 2\ 1\ 0$.

It is known that every permutation can be written in a unique way by an inversion table and that every inversion table $b_1\ b_2\ b_3 \ldots b_n$ in which 0ドル \leq b_i \leq n-i$ holds for all $i \in [n],ドル represents a valid permutation.

Write a program that will convert a inversion table to its corresponding cycle notation.

입력

The input data consists of two lines. The first line contains an integer $n,ドル i.e. the order of a permutation. The second line contains $n$ space-separated integers describing a valid inversion table.

출력

Output one line that contains the cycle notation of the permutation given by the given inversion table. Each cycle should be in parentheses. Cycles should be separated by one space. The numbers within the cycle should also be separated by one space. The smallest element should always be in the first place in the cycle. Cycles should be ordered according to the element in the first place. (See examples.)

제한

• 1ドル \leq n \leq 10^5$

힌트