快速排序

题号：NC53315
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
Special Judge, 64bit IO Format: %lld

题目描述

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

输入描述:

第一行一个整数，表示排列a的大小。
接下来有n个不同的数，表示排列a。

输出描述:

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

示例1

输入

复制

5
3 1 4 2 5

输出

复制

1
1 5

示例2

输入

复制

8
2 4 1 5 3 6 7 8

输出

复制

2
2 6
1 2

示例3

输入

复制

2
2 1

输出

复制

说明

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

备注:

设表示最小操作次数。
对于所有数据，且互不相同。

CC-BY-SA，感谢LOJ分享，译文来自  https://loj.ac/problem/2848