Вам задан массив \(a_1, a_2, \dots, a_n\), в котором \(a_i = i\).
За один шаг, вы можете выбрать две позиции \(x\) и \(y\) (\(x \neq y\)) и присвоить \(a_x = \left\lceil \frac{a_x}{a_y} \right\rceil\) (деление с округлением вверх).
Ваша задача: сделать так, чтобы массив \(a\) состоял из \(n - 1\) единиц и \(1\)-й двойки за не более чем \(n + 5\) шагов. Заметим, что не нужно минимизировать количество шагов.
Выходные данные
Для каждого набора входных данных, выведите список операций, который сделает так, что массив \(a\) станет состоять из \(n - 1\) единиц и \(1\)-й двойки, в следующем формате: сначала, выведите одно число \(m\) (\(m \le n + 5\)) — количество операций; далее выведите \(m\) пар чисел \(x\) и \(y\) (\(1 \le x, y \le n\); \(x \neq y\)) (\(x\) может быть как больше, так и меньше \(y\)) — выбранные позиции на соответствующем шаге.
Можно доказать, что для заданных ограничений всегда возможно найти некоторый список операций.
Примечание
В первом наборе входных данных, у вас есть массив \(a = [1, 2, 3]\). Вы можете сделать, например, следующее:
- выберем \(3\), \(2\): \(a_3 = \left\lceil \frac{a_3}{a_2} \right\rceil = 2\) и массив \(a = [1, 2, 2]\);
- выберем \(3\), \(2\): \(a_3 = \left\lceil \frac{2}{2} \right\rceil = 1\) и массив \(a = [1, 2, 1]\).
Вы получили массив с
\(2\) единицами и
\(1\) двойкой за
\(2\) шага.
Во втором наборе, \(a = [1, 2, 3, 4]\). Вы можете, например, сделать следующее:
- выберем \(3\), \(4\): \(a_3 = \left\lceil \frac{3}{4} \right\rceil = 1\) и массив \(a = [1, 2, 1, 4]\);
- выберем \(4\), \(2\): \(a_4 = \left\lceil \frac{4}{2} \right\rceil = 2\) и массив \(a = [1, 2, 1, 2]\);
- выберем \(4\), \(2\): \(a_4 = \left\lceil \frac{2}{2} \right\rceil = 1\) и массив \(a = [1, 2, 1, 1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3
4
|
2
3 2
3 2
3
3 4
4 2
4 2
|