2848 「ROI 2018 Day 2」快速排序

译自 ROI 2018 Day2 T2. Быстрая сортировка (Quick sort)

给一个包含 $n$ 个元素的排列 $[a_1,$ $a_2,$ $\ldots,$ $a_n]$。
定义操作 $S(l,$ $r),$ 表示：将数列的片段 $[a_l,$ $a_{l+1},$ $\ldots,$ $a_r]$ 重排成 $[a_{l+1},$ $a_{l+3},$ $\ldots,$ $a_l,$ $a_{l+2},$ $\ldots]$。
举个例子：$[2, 4, 1, 5, 3, 6, 7, 8]\xrightarrow{\,S(2,6)\,} [2, 1, 3, 4, 5, 6, 7, 8],$ 其中子串 $[4, 1, 5, 3, 6]$ 被重排成了 $[1, 3, 4, 5, 6]$。
给定一个排列，试求经过多少次操作能使排列变成递增顺序，并输出任意一组方案，不要求方案的操作次数最少，但要求操作次数 $\leqslant 15000$。

第一行一个整数 $n\ \left( 1 \leqslant n \leqslant 3000 \right)$，表示排列 $a$ 的大小。
接下来有 $n$ 个不同的数 $a_1,\ a_2,\ \ldots,\ a_n$，表示排列 $a$。

第一行一个整数 $k$，表示你的操作次数。 需要满足 $0 \leqslant k \leqslant 15000$。
接下来 $k$ 行，你需要按照操作顺序描述你的操作。对于每一步操作，输出两个数 $L$, $R$，表示你对片段 $a_L,\ a_{L+1},\ \ldots,\ a_R$ 执行了一次操作。 需满足 $1 \leqslant L \leqslant R \leqslant n$。
注意，你不需要最小化。你只需保证 $0 \leqslant k \leqslant 15000$ 即可。保证存在这样的 $k$。

显然 $S(1,1)$ 和 $S(2,2)$ 并没有什么卵用 举这个例子是告诉你，不要求方案的操作次数最少。

设 $k_0$ 表示最小操作次数。
对于所有数据，$1\leqslant n\leqslant 3000,$ $0\leqslant k_0\leqslant 15000,$ $1\leqslant a_i\leqslant n,$ 且 $a_i$ 互不相同。