Вам дан массив \(a_1, a_2, \ldots, a_n\) положительных целых чисел.
Вы можете сделать следующую операцию несколько (возможно, ноль) раз:
- Выбираются два индекса \(i\), \(j\) (\(1 \leq i, j \leq n\), \(i \neq j\)).
- Приравнивается \(a_i := \lceil \frac{a_i}{a_j} \rceil\). Здесь \(\lceil x \rceil\) обозначает значение \(x\), округленное вверх до ближайшего целого числа \(\geq x\).
Можно ли сделать все элементы массива равными с помощью нескольких операций (возможно, нуля)? Если да, выведите любой способ сделать это за не более чем \(30n\) операций.
Можно доказать, что в ограничениях этой задачи если существует какой-нибудь способ сделать все элементы равными, существует способ, использующий не более \(30n\) операций.
Выходные данные
Для каждого набора входных данных выведите единственное целое число \(q\) (\(-1 \leq q \leq 30n\)). Если \(q=-1\), то решения не существует, иначе \(q\) равняется количеству операций.
Если \(q \geq 0\), то следующие \(q\) строк содержат по два целых числа \(i\), \(j\) (\(1 \leq i, j \leq n\), \(i \neq j\)) — описания операций.
Если существует несколько решений, выведите любое.
Примечание
В первом, втором и четвертом наборах входных данных все числа равны, поэтому можно ничего не делать.
В третьем наборе входных данных невозможно сделать все числа равными с помощью операций.
В пятом наборе входных данных: \([\color{red}{4}, 3, \color{blue}{2}] \to [\color{blue}{2}, \color{red}{3}, 2] \to [2, 2, 2]\).
В шестом наборе входных данных: \([\color{blue}{3}, 3, \color{red}{4}, 4] \to [3, \color{blue}{3}, 2, \color{red}{4}] \to [\color{red}{3}, 3, \color{blue}{2}, 2] \to [2, \color{red}{3}, 2, \color{blue}{2}] \to [2, 2, 2, 2]\).
На примере красные числа это числа на позициях \(i\) (которые будут присвоены), синие числа это числа на позициях \(j\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
1
100
3
1 1 1
2
2 1
2
5 5
3
4 3 2
4
3 3 4 4
2
2 100
5
5 3 6 7 8
6
3 3 80 3 8 3
4
19 40 19 55
|
0
0
-1
0
2
1 3
2 1
4
3 1
4 2
1 3
2 4
6
2 1
2 1
2 1
2 1
2 1
2 1
8
5 2
4 2
3 2
1 3
1 3
2 1
4 1
5 1
4
5 1
3 1
3 1
3 1
9
4 2
2 1
1 2
1 2
3 2
3 2
1 4
2 4
3 4
|