← 返回题目列表

Codeforces · 109/D

D. 幸运排序

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

Petya 喜欢幸运数字。我们都知道,幸运数字是十进制表示中仅包含幸运数字4和7的正整数。例如,数字47、744、4是幸运数字,而5、17、467则不是幸运数字。

Petya得到了一个由n个数字组成的数组,这是他的生日礼物。现在他想按照非降序排序。然而,通常的排序执行起来很无聊,这就是为什么 Petya 发明了以下限制:一个人可以交换任意两个数字,但前提是其中至少有一个是幸运的。您的任务是根据指定的限制对数组进行排序。找出任何可能的交换序列(序列中的操作数不应超过 2n)。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105) — 数组中的元素数量。第二行包含n个正整数,不超过109——需要按非降序排序的数组。

输出

在第一行打印数字 k (0 ≤ k ≤ 2n) — 排序中交换的数量。在接下来的 k 行中打印一对不同的数字(每行一对)——要交换的元素的索引。数组中的数字从1开始编号。如果无法对给定序列进行排序,则打印单个数字-1。

如果有多个解,则输出任意一个。请注意,您不必最小化 k。任何交换次数不超过 2n 的排序都是可接受的。

示例

输入 #1

2
4 7

输出 #1

0

输入 #2

3
4 2 1

输出 #2

1
1 3

输入 #3

7
77 66 55 44 33 22 11

输出 #3

7
1 7
7 2
2 6
6 7
3 4
5 3
4 5