给定一个由 $$$n$$$ 元素组成的数组 $$$a$$$。您可以对其应用多个操作(可能为零)。
在每次操作期间,您选择两个索引 $$$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$$$ 是数组的结果大小)。
计算使数组严格升序所需的最小操作数。
输入
第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 10000$$$) — 测试用例的数量。
每个测试用例由两行组成。第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 15$$$) — 初始数组 $$$a$$$ 中的元素数量。
第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^6$$$)。
保证:
- 具有 $$$n \ge 5$$$ 的测试用例数量不大于 $$$5000$$$;
- 具有 $$$n \ge 8$$$ 的测试用例数量不大于 $$$500$$$;
- $$$n \ge 10$$$ 的测试用例数量不大于 $$$100$$$;
- 具有 $$$n \ge 11$$$ 的测试用例数量不大于 $$$50$$$;
- $$$n \ge 12$$$ 的测试用例数量不大于 $$$25$$$;
- $$$n \ge 13$$$ 的测试用例数量不大于 $$$10$$$;
- $$$n \ge 14$$$ 的测试用例数量不大于 $$$3$$$;
- 具有 $$$n \ge 15$$$ 的测试用例数量不大于 $$$1$$$。
输出
对于每个测试用例,打印答案如下:
在第一行中,打印 $$$k$$$ — 您必须执行的最少操作数。然后打印$$$k$$$行,每行包含对应操作的两个索引$$$i$$$和$$$j$$$。请注意,从数组中删除元素后,数组中元素的数量会发生变化。如果有多个最佳操作序列,则打印其中任意一个。
示例
输入 #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
输出 #1
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
注意
在第一个测试用例中,操作顺序 $$$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]$$$。