← 返回题目列表

Codeforces · 686/B

B. 小强盗女孩的动物园

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

小强盗女孩喜欢在动物园里吓唬动物来取乐。她决定将动物按照高度不降低的顺序排列成一排。然而,动物们太害怕了,无法呆在正确的地方。

强盗女孩一开始很生气,但后来她决定自己安排动物。她反复命名数字 l 和 r,使得 r - l + 1 是偶数。之后,占据l和r之间位置的动物重新排列如下:位置l的动物与位置l+1的动物交换位置,l+2的动物与位置l+3的动物交换,……,最后位置r-1的动物与位置r的动物交换。

帮助强盗女孩按照身高不减的顺序排列动物。您最多应说出 20 000 个片段,否则强盗女孩会感到无聊并再次开始吓唬动物。

输入

第一行包含一个整数 n (1 ≤ n ≤ 100) — 强盗女孩动物园中的动物数量。

第二行包含 n 个空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ 109),其中 ai 是占据第 i 个位置的动物的高度。

输出

打印通过不降低高度重新排列动物的操作顺序。

输出应包含多行,第 i 行应包含两个空格分隔的整数 li 和 ri (1 ≤ li < ri ≤ n) - 强盗女孩应命名的段的描述。应按照操作执行的顺序来描述段。

操作次数不应超过 20 000 次。

如果动物从一开始就排列正确,则允许您不输出任何内容。

示例

输入 #1

4
2 1 4 3

输出 #1

1 4

输入 #2

7
36 28 57 39 66 69 68

输出 #2

1 4
6 7

输入 #3

5
1 2 1 2 1

输出 #3

2 5
3 4
1 4
1 4

注意

请注意,您不必最小化操作次数。允许执行最多 20 000 次操作的任何解决方案。