在此问题中,您的目标是在最多 n 次交换中对由 n 个整数组成的数组进行排序。对于给定的数组,找到使数组按非降序排序的交换序列。交换是连续进行的,一个接一个。
请注意,在这个问题中,您不必最小化交换次数 - 您的任务是找到任何不长于 n 的序列。
输入
输入的第一行包含整数 n (1 ≤ n ≤ 3000) — 数组元素的数量。第二行包含数组元素:a0, a1, ..., an - 1 (- 109 ≤ ai ≤ 109),其中 ai 是数组的第 i 个元素。元素从左到右从 0 到 n - 1 编号。某些整数可能在数组中出现多次。
输出
在第一行打印 k (0 ≤ k ≤ n) — 交换次数。接下来的 k 行必须包含 k 个交换的描述,每行一个。每个交换应打印为一对整数 i, j (0 ≤ i, j ≤ n - 1),表示元素 ai 和 aj 的交换。您可以按任意顺序打印成对的索引。交换按照它们在输出中出现的顺序执行,从第一个到最后一个。允许打印 i = j 并多次交换同一对元素。
如果有多个答案,请打印其中任何一个。保证至少存在一个答案。
示例
输入 #1
5 5 2 5 1 4
输出 #1
2 0 3 4 2
输入 #2
6 10 20 20 40 60 60
输出 #2
0
输入 #3
2 101 100
输出 #3
1 0 1