← 返回题目列表

Codeforces · 339/E

E. 三个交换

中文机器翻译题面 查看原题

马饲养员 Xenia 有 n (n > 1) 匹排成一排的马。每匹马都有自己独特的编号。最初,第 i 匹左马的编号为 i。也就是说,一排马的编号顺序如下(从左到右):1、2、3、...、n。

Xenia 在表演前训练马匹。在练习过程中,她不断地向他们发出命令。每个命令都是一对数字 l, r (1 ≤ l < r ≤ n)。命令l,r表示左起第l,第(l + 1),第(l + 2),...,第r位的马必须重新排列。最初站在第 l 和第 r 位的马将会交换。第 (l + 1) 位和第 (r - 1) 位的马将交换。第 (l + 2) 位和第 (r - 2) 位的马将交换,依此类推。换句话说,[l,r] 段上的马将顺序更改为相反的顺序。

例如,如果 Xenia 命令 l = 2,r = 5,并且命令之前的马匹数量序列为 (2, 1, 3, 4, 5, 6),那么命令之后的序列将为 (2, 5, 4, 3, 1, 6)。

我们知道,在练习过程中,Xenia 最多给出了三个所描述形式的命令。练习结束时,您已经得到了马匹数量的最终序列。查找 Xenia 在练习过程中发出的命令。请注意,您不需要最小化解决方案中的命令数量,只需找到最多三个命令的任何有效序列。

输入

第一行包含一个整数 n (2 ≤ n ≤ 1000) — 该行中的马数。第二行包含 n 个不同的整数 a1, a2, ..., an (1 ≤ ai ≤ n),其中 ai 是练习后该行中第 i 个左马的编号。

输出

第一行应包含整数 k (0 ≤ k ≤ 3) — Xenia 在练习过程中给出的逗号数量。在接下来的 k 行中,每一行打印两个整数。在第 i 行中打印数字 li, ri (1 ≤ li < ri ≤ n) — Xenia 在练习过程中的第 i 个命令。

保证存在解。如果有多个解决方案,您可以打印其中任何一个。

示例

输入 #1

5
1 4 3 2 5

输出 #1

1
2 4

输入 #2

6
2 1 4 3 6 5

输出 #2

3
1 2
3 4
5 6