Background

Simplified statement: $\texttt{Link}$。

Why don’t you go solve this problem after finishing this one?

Problem Description

You need to sort a permutation of $1\sim n$ on a strange computer.

You may choose a number $x$. Then each time, you may reverse a segment of length $x+1$ or a segment of length $x-1$.

Please restore the sequence to $1\sim n$ within $20\times n$ operations.

(Setter’s note: The current best can be under 15000 operations. Please try to optimize your algorithm.)

Input Format

The input consists of $2$ lines.

The first line contains an integer $n$.

The second line contains $n$ integers, representing the sequence $a$.

Output Format

The output consists of $m + 2$ lines.

The first two lines each contain $1$ integer, which are $x,m$ respectively. Here, $m$ is the number of operations.

The next $m$ lines each contain two integers, representing the left and right endpoints of the reversed interval.

This problem uses $\text{SPJ}$, and you will be judged as long as the reverse operations are correct.

2
2 1

1
1
1 2

5
5 2 3 4 1

4
2
1 5
2 4

Hint

• Sample $1$ explanation:

  Reverse $(1,2)$, and the sequence becomes $1,2$.

• Sample $2$ explanation:

  Reverse $(1,5)$, and the sequence becomes $1,4,3,2,5$.

  Reverse $(2,4)$, and the sequence becomes $1,2,3,4,5$.

This problem uses bundled Subtask tests.

For $100\%$ of the testdata, $1\le n,a_i\le 10^3$, and the data guarantees that $a$ is a permutation of $1\sim n$.

Translated by ChatGPT 5