Петя любит счастливые числа. Всем известно, что счастливыми являются положительные целые числа, в десятичной записи которых содержатся только счастливые цифры 4 и 7. Например, числа 47, 744, 4 являются счастливыми, а 5, 17, 467 — не являются.
Пете на день рождения подарили массив из n чисел. Сейчас он хочет отсортировать его по неубыванию. Но выполнять обычную сортировку скучно, поэтому Петя придумал ограничение: можно менять местами любые два числа, но только если хотя бы одно из них — счастливое. Ваша задача — отсортировать массив, учитывая заданное ограничение. Найдите любую возможную последовательность обменов, количество операций в которой не превышает 2n.
В первой строке задано одно целое число n (1 ≤ n ≤ 105) — количество элементов массива. Во второй строке заданы n целых положительных чисел, не превосходящих 109 — массив, который нужно отсортировать по неубыванию.
В первой строке выведите число k (0 ≤ k ≤ 2n) — количество обменов в сортировке. В следующих k строках выведите по одной паре различных чисел — номера элементов, которые нужно обменять местами. Числа в массиве нумеруются начиная с единицы. Если сортировка невозможна, выведите единственное число -1.
Если решений несколько, выведите любое. Обратите внимание, что минимизировать k не требуется. Подойдет любая сортировка, количество обменов в которой не превышает 2n.
2
4 7
0
3
4 2 1
1
1 3
7
77 66 55 44 33 22 11
7
1 7
7 2
2 6
6 7
3 4
5 3
4 5
| Codeforces Beta Round 84 (Div. 1 Only) |
|---|
| Закончено |
