Problem Description

It is the year 20XX, and the world is a dystopia ruled by the Distributed AtC◯der Corporation. Currently, people's entertainment is limited to programming contests that focus on distributed and parallel processing. For example, it is a common sight to see families visiting supercomputers (via ssh) on weekends. (Problem statement reference: UTPC 2011 Problem A)

(Actually, the problem setting described below is more about parallel processing than distributed processing, and it's more like Parallel Sorting than Distributed Sorting. However, the initial 'D' works better for us, and since we're already making excuses here, and anyway, today is Christmas, so we don't care about the details.)

In distributed and parallel processing, even basic operations can involve a wide variety of tricks. For example, consider sorting an array of $ N $ distinct integers $ X_1 $, $ X_2 $, ..., $ X_N $ in ascending order.

For sorting, we use a machine that allows the following type of operation:

• Operation: Given $ 2k $ distinct indices $ A_1 $, $ A_2 $, ..., $ A_{2k} $, for each $ i $ ($1 \leq i \leq k$), swap the values $ X_{A_{2i-1}} $ and $ X_{A_{2i}} $ (the $ A_{2i-1} $th and $ A_{2i} $th elements of $ X $). Each $ j $ ($1 \leq j \leq 2k$) must satisfy $1 \leq A_j \leq N$.

For example, when $ X = (5, 3, 1, 2, 4) $ and $ k = 2 $, $ (A_1, A_2, A_3, A_4) = (1, 3), (2, 4) $, the operation results in $ X = (1, 2, 5, 3, 4) $.

Using only this operation, write a program to find the minimum number of operations needed to sort $ X $ in ascending order and output one procedure that sorts $ X $ in the minimum number of operations.

Input Format

The input is given from the standard input in the following format:

$ N $ $ X_1 $ $ X_2 $ ... $ X_N $

Output Format

Output the minimum number of operations needed to sort $ X $ in ascending order on the first line, followed by the details of each operation, one per line.

At the beginning of each line representing an operation, output the number of pairs $ k $ to swap. Then, followed by a space, output the $ 2k $ integers $ A_1 $, $ A_2 $, ..., $ A_{2k} $ separated by spaces.

Sample Input and Output

Sample Input #1

3
2 3 1

Sample Output #1

2
1 1 3
1 2 3

Sample Input #2

3
1 2 3

Sample Output #2

0

Sample Input #3

5
5 4 3 2 1

Sample Output #3

1
2 1 5 2 4

Notes/Hints

Constraints

• $1 \leq N \leq 10^5$.
• $1 \leq X_i \leq 10^9$.
• $ X_i $ are distinct integers.

Sample Explanation 1

As long as the number of operations is minimal and the array is correctly sorted in ascending order, outputs other than this will also be considered correct. For example, for this input, an output like 2 1 1 2 1 3 1 is also considered correct.

见题面 Input 部分

见题面 Output 部分