← 返回题目列表

Codeforces · 1635/C

C. 差异排序

中文机器翻译题面 查看原题

给定一个包含 $$$n$$$ 元素的数组 $$$a$$$。

您可以执行以下操作不超过 $$$n$$$ 次:选择三个索引 $$$x,y,z$$$ $$$(1 \leq x < y < z \leq n)$$$ 并将 $$$a_x$$$ 替换为 $$$a_y - a_z$$$。运算后$$$|a_x|$$$需要小于$$$10^{18}$$$。

您的目标是使结果数组不递减。如果有多个解决方案,则可以输出任何一个。如果无法实现,也应该报告。

输入

每个测试包含多个测试用例。第一行将包含一个整数 $$$t$$$ $$$(1 \leq t \leq 10000)$$$ — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ $$$(3 \leq n \leq 2 \cdot 10^5)$$$ — 数组 $$$a$$$ 的大小。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots ,a_n$$$ $$$(-10^9 \leq a_i \leq 10^9)$$$,$$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果没有解决方案,则在一行中打印 $$$-1$$$。否则,在第一行中,您应该打印一个整数 $$$m$$$ $$$(0 \leq m \leq n)$$$ — 您执行的操作数。

那么接下来的 $$$m$$$ 行中的第 $$$i$$$ 行应包含三个整数 $$$x,y,z$$$ $$$(1 \leq x < y < z \leq n)$$$— 第 $$$i$$$ 操作的描述。

如果有多个解,则可以输出任何一个。请注意,您不必最小化此任务中的操作数量。

示例

输入 #1

3
5
5 -4 2 -1 2
3
4 3 2
3
-3 -2 -1

输出 #1

2
1 2 3
3 4 5
-1
0

注意

在第一个示例中,数组变为

$$$[-6,-4,2,-1,2]$$$ 第一次操作后,

$$$[-6,-4,-3,-1,2]$$$ 第二次操作后。

在第二个示例中,不可能在任何操作序列之后对数组进行排序。

在第三个示例中,数组已经排序,因此我们不需要执行任何操作。