题目描述

由于你是排序大师，你经常被路过的游客刁难，要求用一些奇怪的操作给序列排序。

由于你是远近闻名的排序大师，邻国的排序萌新小 I 慕名前来拜访，留下了一个长度为 $n$ 的排列 $a_1, a_2 \cdots, a_n$，并要求你用以下操作将排列升序排序：

• 定义 $a_{i \sim j} = \{a_i,a_{i+1},\cdots, a_j\}$。选定 $1 \le i \le j < k \le l \le n$，交换 $a_{i \sim j}$ 和 $a_{k \sim l}$，即交换过后序列变为 $a_{1 \sim i-1}, a_{k \sim l}, a_{j+1 \sim k-1}, a_{i \sim j}, a_{l+1 \sim n}$。

由于你是因精益求精而远近闻名的排序大师，你需要给出一个排序方案最小化操作次数。

输入格式

输入的第一行一个整数 $n(1 \le n \le 2000)$ 表示序列长度，第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n (1 \le a_i \le n)$ 描述排列。

输出格式

输出的第一行一个整数 $s$ 表示你给出的方案的步数，接下来 $s$ 行每行四个整数 $i,j,k,l$ 表示一次操作。若有多个方案，输出任意一个即可。

6
1 4 5 3 2 6

1
2 3 5 5

提示

样例 #1 解释

选定 $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}}$ 变为 $\colorbox{white}{\color{black}{1}\color{red}{2}\color{black}{3}\color{blue}{45}\color{black}{6}}$。

题目使用协议

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2024 初赛 官方仓库（https://github.com/ckw20/thupc2024_pre_public）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；

2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；

3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。