排序

题目描述

众所周知，排序方法有许多种。例如：简单易懂的冒泡排序，平均复杂度较优的快速排序，以及不基于比较的基数排序等等。

现在，小 $D$ 得到了一个自然数序列 $\{a_1,a_2,\cdots,a_n\}$。他想要对其按照从小到大的顺序进行排序（即使得每个元素均严格不大于他的后继元素）。但由于基于比较的排序算法复杂度下界已经被证明为 $\Theta (n\log_2n)$，所以小 $D$ 决定尝试一种全新的排序算法：翻转排序。

在翻转排序中，小 $D$ 在每次操作中，可以选择一个区间 $[l,r]$ $(1\le l\le r\le n)$，并翻转 $a_l,a_{l+1},\cdots,a_r$。即，在该次操作完后，序列将会变为 $a_1,a_2,\cdots,a_{l-1},a_r,a_{r-1},\cdots,a_{l+1},a_l,a_{r+1},a_{r+2},\cdots,a_n$。

例如，对于序列 $[1,6,2,4,3,5]$，若选择区间 $[2,4]$ 进行翻转，则将会得到 $[1,4,2,6,3,5]$。

定义一次操作的代价为 $r-l+1$，即翻转的区间长度。定义一个操作序列的代价为每次操作的代价之和。现在，请你帮助小 $D$ 求出一个代价足够小的操作序列（你并不一定要求出代价最小的操作序列）。

输入格式

第一行一个正整数 $n$，表示序列长度。

第二行 $n$ 个空格隔开的非负整数，表示小 $D$ 得到的自然数序列 $a_1,a_2,\cdots,a_n$。

输出格式

输出若干行，每行两个空格隔开的正整数 $l,r$ $(1\le l\le r\le n)$，表示一次翻转区间 $[l,r]$ 的操作。

最后输出一行 -1 -1，标志着操作序列的结束。

样例输入

4
1 3 2 4

样例输出

2 3
-1 -1

样例解释

在一次操作 $[2,3]$ 后，序列变为 $[1,3,2,4]$，满足从小到大排列的要求。因此这是一种合法的输出，且代价为 $3-2+1=2$。

因为你可以自行生成数据并判断你的输出是否正确（见 “评分方式” 一节），故本题不再提供更多的样例数据。

评分方式

对于每个测试点，若你的输出格式符合题目要求，且输出的操作序列可以将输入的序列按照从小到大的顺序排序，并且该操作序列的代价不超过 $2\times 10^7$，则该测试点得满分，否则不得分。

下发文件中提供了 checker.cpp，该程序将对于其所在目录下的 sort.in，判断其所在目录下的 sort.out 是否为一个正确的操作序列。若正确，将给出该操作序列的代价。若不正确，将给出错误信息。选手可以借助该程序来更好地检查自己的程序是否正确。

运行时，必须保证 sort.in 为一个合法的输入，且需保证 sort.out 符合题目中描述的输出格式，否则出现任何结果均有可能。

数据规模与约定

本题共 $20$ 个测试数据，每个测试数据 $5$ 分。

对于所有测试数据，保证 $1\le n\le 50000$，且 $0\le a_i\le 10^9$。以下为每个测试数据的数据范围及性质：

其中，若 “特殊性质 $\ast$” 一栏为 “$\surd$”，则保证该测试数据中：输入的序列 $a_1,a_2,\cdots,a_n$ 仅由 $0$ 或 $1$ 组成。否则不保证这一点成立。

友情提示：本题输出数据量可能较大，对于 C++ 选手，请不要使用 (std::)endl 进行换行。一种替代方法为 "\n"，例如使用 std::cout << x << "\n"; 而非 std::cout << x << std::endl;，否则可能导致超时。

时间限制：$2\mathtt{s}$

空间限制：$512\mathtt{MB}$

checker.cpp

checker.cpp