Дан массив \(a\), состоящий из \(n\) целых чисел. Вы можете применить несколько операций к этому массиву (возможно, ни одной).
Во время каждой операции вы выбираете два индекса \(i\) и \(j\) (\(1 \le i, j \le n\); \(i \ne j\)), увеличиваете \(a_j\) на \(a_i\), а затем удаляете \(i\)-й элемент из массива (при этом индексы всех элементов правее удаляемого уменьшаются на \(1\), и размер массива \(n\) также уменьшается на \(1\)).
Ваша цель — сделать массив \(a\) строго возрастающим, то есть должно выполняться условие \(a_1 < a_2 < \dots < a_n\) (где \(n\) — итоговый размер массива).
Посчитайте минимальное количество операций, которое требуется, чтобы массив стал возрастающим.
Выходные данные
На каждый набор тестовых данных выведите ответ следующим образом:
Сначала выведите \(k\) — минимальное количество операций, которые вы должны сделать. Затем выведите \(k\) строк, каждая из которых содержит два индекса \(i\) и \(j\) для соответствующей операции. Обратите внимание, что нумерация элементов меняется после удаления элемента из массива. Если существует несколько оптимальных последовательностей операций, выведите любую из них.
Примечание
В первом наборе тестовых данных \(a\) меняется следующим образом:
\([2, 1, 3, 5, 1, 2, 4, 5] \rightarrow [2, 1, 3, 5, 1, 4, 7] \rightarrow [1, 3, 5, 1, 6, 7] \rightarrow [2, 3, 5, 6, 7]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
8
2 1 3 5 1 2 4 5
15
16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1
2
3 3
14
1 2 3 4 5 6 7 8 9 10 11 12 13 14
|
3
6 8
1 6
4 1
7
1 15
1 13
1 11
1 9
1 7
1 5
1 3
1
2 1
0
|