CF1854A2 Dual (Hard Version)

[Popskyy & tiasu - Dual](https://soundcloud.com/popskyy/popskyy-tiasu-dual) ⠀ 本题的两个版本唯一的区别在于操作次数的最大限制。只有在所有版本都被解决的情况下，你才能进行 hack。 给定一个整数数组 $a_1, a_2, \dots, a_n$（元素可以为正、负或 $0$）。你可以对数组进行多次操作（也可以不进行操作）。 每次操作，你可以选择 $i, j$（$1 \leq i, j \leq n$，允许 $i = j$），并将 $a_j$ 加到 $a_i$ 上（即 $a_i := a_i + a_j$）。 请在最多 $31$ 次操作内，使数组变为非递减（即对于 $1 \leq i \leq n-1$，有 $a_i \leq a_{i+1}$）。你不需要最小化操作次数。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 500$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 20$），表示数组的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-20 \leq a_i \leq 20$），表示操作前的数组。

对于每个测试用例，按如下格式输出你的操作。 第一行输出一个整数 $k$（$0 \leq k \leq 31$），表示操作次数。 接下来的 $k$ 行，每行包含两个整数 $i$ 和 $j$（$1 \leq i, j \leq n$），表示将 $a_j$ 加到 $a_i$ 上的操作。 所有操作完成后，数组 $a_1, a_2, \dots, a_n$ 必须是非递减的。

在第一个测试用例中，通过将 $a_1 = 2$ 加到 $a_2$ 上，得到数组 $[2, 3]$，已经是非递减的。 在第二个测试用例中，数组变化如下： - $[1, 2, -10, 3]$ - $[1, 2, -10, 6]$ - $[1, 2, -10, 12]$ - $[1, 2, 2, 12]$ 在第三个测试用例中，最终数组为 $[2, 3, 3, 3, 3]$。 由 ChatGPT 4.1 翻译