H. Toy Marbles
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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
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
Note

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.