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$, and so on. Since the top row is always $1\ 2\ 3\ \ldots\ n$, we usually omit it and write 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$. We keep doing this until we 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, which is $2$ in this case, and repeat the process. Eventually, we obtain 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 elements that are greater than $i$ and appear to the left of $i$ in the one-line notation. In our example, the inversion table is:

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

Every permutation can be written in exactly one way as an inversion table, and every inversion table $b_1\ b_2\ b_3\ \ldots\ b_n$ with $0 \leq b_i \leq n-i$ for all $i \in [n]$ represents a valid permutation.

Write a program that converts an inversion table to its corresponding cycle notation.

The first line contains an integer $n$, 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 inversion table. Each cycle is enclosed in parentheses. Cycles are separated by one space. The numbers within a cycle are separated by one space. The smallest element always comes first in each cycle. Cycles are ordered by their first element. See the examples.

$1 \leq n \leq 10^5$