Problem E. Shift Sort

时间限制：1000ms

空间限制：256MB

题目描述

给定一个长度为 $n$ 的序列 $[a_1, a_2, a_3, ..., a_n]$。

每次操作可以选择一段连续子序列 $[a_l, a_{l+1}, .., a_{r-1}, a_{r}]$ 令其左移一位，操作完后变为 $[a_{l+1}, a_{l+2}, ..., a_{r-1}, a_{r}, a_{l}]$。

现在请给出一个操作序列，使该序列经过若干次操作后变为有序序列。尝试在 $n$ 次内完成这个任务，可以证明在 $n$ 次操作内一定可以使这个序列变为有序序列。

输入描述

第一行输入一个整数 $n$，代表序列长度。

第二行输入 $n$ 个整数 $a_1, a_2, ..., a_n$，代表序列中的数。

输出描述

输出一个整数 $T$，代表操作次数，需要满足 $1 \le T \le n$；

接下来 $T$ 行每行两个整数 $l$ 和 $r$，代表将连续子序列 $[a_l, a_{l+1}, ..., a_{r-1}, a_{r}]$ 进行一次左移操作，需要满足 $1 \le l \le r \le n$.

样例1

输入

5
2 5 3 1 4

输出

4
2 4
4 5
2 3
1 2

样例1解释

对于给定序列 $[2, 5, 3, 1,4]$，操作 $[2, 4]$ 后变为 $[2, 3, 1, 5, 4]$;

操作 $[4, 5]$ 后变为 $[2, 3, 1, 4, 5]$;

操作 $[2, 3]$ 后变为 $[2, 1, 3, 4, 5]$;

操作 $[1, 2]$ 后变为 $[1, 2, 3, 4, 5]$.

数据范围与约定

$1 \le n \le 1000$，$1 \le a_i \le 10^9$，保证序列中的数互不相同。

输出约定见输出描述。