小强盗女孩喜欢在动物园里吓唬动物来取乐。她决定将动物按照高度不降低的顺序排列成一排。然而,动物们太害怕了,无法呆在正确的地方。
强盗女孩一开始很生气,但后来她决定自己安排动物。她反复命名数字 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 次操作的任何解决方案。