B. 抓娃娃排序

Arcade Crane

时间限制：2 秒 · 内存限制：1024 MiB

原题：NWERC 2025 A · 查看官方英文原文（英文 PDF 也已作为本题附件提供）

题目描述

一台抓娃娃机中有 $n$ 个排成一行的玩偶。它们的可爱程度互不相同，恰好为 $1$ 到 $n$。你希望将它们按可爱程度从小到大排列。

每次操作，你可以抓起当前序列中连续的三个玩偶，在不改变这三个玩偶内部顺序的前提下，将这一整块重新插入序列中的任意位置。其他玩偶可以整体移动来腾出位置，但它们彼此的相对顺序不变。

你最多可以操作 $5000$ 次。请给出一种完成排序的方法。可以证明，在题目约束下总存在满足操作次数限制的方案。

输入格式

第一行包含一个整数 $n$（$5 \leq n \leq 1000$）。

第二行包含 $n$ 个互不相同的整数 $a_{1}, \ldots , a_{n}$（$1 \leq a_{j} \leq n$），表示玩偶当前的排列。

输出格式

第一行输出操作次数 $q$（$0 \leq q \leq 5000$），随后 $q$ 行按顺序各输出一对整数 $i$、$j$（$1 \leq i, j \leq n-2$）。

一次操作中的 $i$ 表示抓起操作前位于第 $i$、$i+1$、$i+2$ 个位置的三个玩偶；$j$ 表示这三个玩偶在操作完成后位于第 $j$、$j+1$、$j+2$ 个位置。位置均从 $1$ 开始编号。

允许 $i = j$，即不改变排列。你不必最小化操作次数；有多种合法方案时输出任意一种即可。

样例

5
3 5 2 1 4

3
2 1
3 1
2 3

6
6 5 4 3 2 1

4
1 3
2 4
3 4
1 3

9
9 2 8 5 4 6 7 3 1

5
2 6
5 1
2 7
5 3
1 3

5
1 2 3 4 5

1
2 2

原题版权归原作者及相应赛事评委会所有，采用 CC BY-SA 4.0 许可。中文译文为本练习赛整理，按相同许可发布。题号及中文标题作了调整，输入约束、样例和判题要求依照官方原题；图示及完整英文叙述请参阅英文原文附件。