Problem Description

Since you are a sorting master, you are often challenged by passing tourists, who ask you to sort a sequence using some strange operations.

Since you are a well-known sorting master, a sorting beginner from a neighboring country, Little I, came to visit you and left behind a permutation $a_1, a_2 \cdots, a_n$ of length $n$, asking you to sort the permutation in ascending order using the following operation:

• Define $a_{i \sim j} = \{a_i,a_{i+1},\cdots, a_j\}$. Choose $1 \le i \le j < k \le l \le n$, and swap $a_{i \sim j}$ and $a_{k \sim l}$. That is, after swapping, the sequence becomes $a_{1 \sim i-1}, a_{k \sim l}, a_{j+1 \sim k-1}, a_{i \sim j}, a_{l+1 \sim n}$.

Since you are a well-known sorting master who always strives for perfection, you need to provide a sorting plan that minimizes the number of operations.

Input Format

The first line contains an integer $n(1 \le n \le 2000)$, representing the length of the sequence. The second line contains $n$ integers $a_1,a_2,\cdots,a_n (1 \le a_i \le n)$, describing the permutation.

Output Format

The first line outputs an integer $s$, representing the number of steps in your plan. The next $s$ lines each output four integers $i,j,k,l$, representing one operation. If there are multiple plans, output any one of them.

6
1 4 5 3 2 6

1
2 3 5 5

Hint

Sample #1 Explanation

Choose $i = 2, j = 3, k = 5, l = 5$. $\colorbox{white}{\color{black}{1}\color{blue}{45}\color{black}{3}\color{red}{2}\color{black}{6}}$ becomes $\colorbox{white}{\color{black}{1}\color{red}{2}\color{black}{3}\color{blue}{45}\color{black}{6}}$.

Problem License

From the THUPC2024 (Tsinghua University Student Programming Contest and Collegiate Invitational Contest 2024) Preliminary Round.

In the following, "this repository" refers to the official repository of the THUPC2024 Preliminary Round (https://github.com/ckw20/thupc2024_pre_public).

1. Any organization or individual may use or repost the problems in this repository for free.

2. When using the problems in this repository, any organization or individual should do so free of charge and publicly. It is strictly forbidden to use these problems for profit or to add special access restrictions to these problems.

3. If possible, when using the problems in this repository, please also provide how to obtain resources such as testdata, reference solutions, and editorials. Otherwise, please attach the GitHub address of this repository.

Translated by ChatGPT 5