快速排序

译自 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$ 。

第一行一个整数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。

详情