Busy Beaver has discovered that someone has mixed up his toy marbles!
There are $N$ containers, numbered from $1$ to $N$. The $i$-th container currently contains a single marble of color $c_i$.
Busy Beaver wants to tidy up his marbles so that the $i$-th container only contains marbles of color $i$. To achieve this, he can perform either of the following actions any number of times (possibly zero):
- Swap the marbles in two containers $x$ and $y$. After this action, all marbles from container $x$ move to container $y$, and vice versa.
- Move all the marbles from one container $y$ to another container $x$. After this action, container $y$ becomes empty, and all its marbles are moved to container $x$.
Find a way to organize the marbles using the minimum number of actions.
Input
The first line contains an integer $N$ ($1 \leq N \leq 2 \cdot 10^5$)~--- the number of containers.
The second line contains $N$ integers $c_1, c_2, \dots, c_N$ ($1 \leq c_i \leq N$)~--- the marble initially in each container.
Output
On the first line, print a single integer $K$~--- the minimum number of actions required.
On the next $K$ lines, describe the actions in order, one per line. Each action should be in one of the following formats:
- $\texttt{1}~\,x~\,y$: Swap the marbles in containers $x$ and $y$ ($1 \leq x, y \leq N$; $x \neq y$).
- $\texttt{2}~\,x~\,y$: Move all marbles from container $y$ to container $x$ ($1 \leq x, y \leq N$; $x \neq y$).
If there are multiple ways to achieve the goal in the minimum number of actions, you may print any valid solution.
Scoring
There are two subtasks for this problem.
- ($20$ points) All $c_i$ are distinct.
- ($80$ points) No additional constraints.
Examples
Input
4 2 4 3 1
Output
2 1 2 4 1 1 2
Explanation
In the first test case, it is able to achieve the goal in two actions:
- Swap the marbles in containers $2$ and $4$.
- Swap the marbles in containers $1$ and $2$.
It is impossible to achieve the goal in less than two actions.
Input
8 3 6 7 6 3 6 8 3
Output
6 2 6 4 2 6 2 1 8 7 1 7 3 2 3 1 2 3 5