Background

It's my fiesta.

Before one match, kid was defeated on the map of WFOIR1; after one match, kid got up from where he fell.

kid succeeded; he is no longer who he used to be.

Simplified statement: $\texttt{Link}$.

After finishing this problem, why not go solve this problem as well?

Problem Description

kid needs to sort a permutation of $1 \sim n$ on a strange computer, and the next save point will only appear later.

kid can choose a number $x$. Then, in each subsequent operation, kid may cyclically shift a subarray of length $x$ to the left or to the right (the leftmost / rightmost element moves to the rightmost / leftmost position). The shift amount is $1$.

If kid performs more than $23 \times n$ operations, the permutation will explode and kid will fall again. Therefore, please tell kid a way to restore the sequence; leave the remaining operations to €€£!

Input Format

The input has $2$ lines:

The first line contains an integer $n$, representing the length of the sequence.

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

Output Format

The output has $m + 2$ lines.

The first two lines each contain one number, which are $x$ and $m$ respectively. $m$ is the number of operations.

The next $m$ lines each contain two numbers: the first is the left endpoint of the shifted interval, and the second is the direction, where $0$ means shifting left and $1$ means shifting right.

This problem uses $\text{SPJ}$. You will get accepted as long as the cyclic shift operations are correct.

3
2 3 1

2
2
2 0
1 0

5
4 2 3 5 1

3
3
3 1
1 1
2 0

Hint

• Explanation for Sample $1$:

  Shift left on interval $(2,3)$, the sequence becomes $2,1,3$.

  Shift left on interval $(1,2)$, the sequence becomes $1,2,3$.

• Explanation for Sample $2$:

  Shift right on interval $(3,5)$, the sequence becomes $4,2,1,3,5$.

  Shift right on interval $(1,3)$, the sequence becomes $1,4,2,3,5$.

  Shift left on interval $(2,4)$, the sequence becomes $1,2,3,4,5$.

This problem uses bundled Subtasks.

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