A2. Dual (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Popskyy & tiasu - Dual
⠀

Единственное различие между двумя версиями этой задачи — ограничение на максимальное количество операций. Делать взломы можно только в том случае, если решены обе версии задачи.

Вам дан массив $$$a_1, a_2,\dots, a_n$$$ целых чисел (положительных, отрицательных или $$$0$$$). Вы можете выполнить над массивом несколько операций (возможно, $$$0$$$).

Операция производится так: выбираются $$$i, j$$$ ($$$1 \leq i, j \leq n$$$, они могут быть равны) и задается $$$a_i := a_i + a_j$$$ (т.е. к $$$a_i$$$ прибавляется $$$a_j$$$).

Сделайте массив неубывающим (т.е. $$$a_i \leq a_{i+1}$$$ для $$$1 \leq i \leq n-1$$$) не более чем за $$$31$$$ операций. Минимизировать количество операций не требуется.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 20$$$) — длину массива.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-20 \le a_i \le 20$$$) — массив перед выполнением операций.

Выходные данные

Для каждого набора входных данных выведите свои операции в следующем формате:

Первая строка должна содержать целое число $$$k$$$ ($$$0 \le k \le 31$$$) — количество операций.

Следующие $$$k$$$ строк представляют собой $$$k$$$ операций по порядку. Каждая из этих $$$k$$$ строк должна содержать два целых числа $$$i$$$ и $$$j$$$ ($$$1 \leq i, j \leq n$$$) — соответствующая операция заключается в прибавлении $$$a_j$$$ к $$$a_i$$$.

После всех операций массив $$$a_1, a_2,\dots, a_n$$$ должен быть неубывающим.

Пример
Входные данные
10
2
2 1
4
1 2 -10 3
5
2 1 1 1 1
8
0 0 0 0 0 0 0 0
5
1 2 -4 3 -10
10
11 12 13 14 15 -15 -16 -17 -18 -19
7
1 9 3 -4 -3 -2 -1
3
10 9 8
20
1 -14 2 -10 6 -5 10 -13 10 7 -14 19 -5 19 1 18 -16 -7 12 8
20
-15 -17 -13 8 14 -13 10 -4 11 -4 -16 -6 15 -4 -2 7 -9 5 -5 17
Выходные данные
1
2 1
3
4 4
4 4
3 4
4
2 1
3 1
4 1
5 1
0
7
3 4
3 4
5 4
5 4
5 4
5 4
5 4
15
6 1
6 1
6 1
7 2
7 2
7 2
8 3
8 3
8 3
9 4
9 4
9 4
10 5
10 5
10 5
8
3 4
3 4
2 4
2 4
2 4
2 4
1 4
1 4
3
2 1
3 1
3 1
31
14 1
18 7
13 11
15 11
6 4
5 17
19 6
19 12
10 5
11 12
1 17
15 19
16 10
14 2
16 11
20 7
7 6
9 5
3 6
6 14
17 18
18 14
12 3
17 16
8 18
13 16
9 8
14 8
16 2
11 8
12 7
31
5 12
19 13
9 1
5 17
18 19
6 16
15 8
6 9
15 14
7 10
19 7
17 20
14 4
15 20
4 3
1 8
16 12
16 15
5 6
12 10
11 15
20 3
20 19
13 14
11 14
18 10
7 3
12 17
4 7
13 2
11 13
Примечание

В первом наборе входных данных, добавив к $$$a_2$$$ $$$a_1 = 2$$$, получим массив $$$[2, 3]$$$, который является неубывающим.

Во втором наборе входных данных массив изменяется следующим образом:

  • $$$[1, 2, -10, 3]$$$
  • $$$[1, 2, -10, 6]$$$
  • $$$[1, 2, -10, 12]$$$
  • $$$[1, 2, 2, 12]$$$

В третьем наборе входных данных итоговый массив имеет вид $$$[2, 3, 3, 3, 3]$$$.