CF1635C Differential Sorting

给定一个长度为 $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)$，表示测试用例的数量。 每个测试用例的第一行包含一个整数 $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$ 行，每行输出三个整数 $x, y, z$ $(1 \leq x < y < z \leq n)$，表示每次操作的下标。 如果有多种方案，可以输出任意一种。注意本题不要求操作次数最少。

在第一个样例中，第一次操作后数组变为 $[-6, -4, 2, -1, 2]$， 第二次操作后数组变为 $[-6, -4, -3, -1, 2]$。 在第二个样例中，无论进行怎样的操作，都无法使数组有序。 在第三个样例中，数组本身已经有序，因此无需进行任何操作。 由 ChatGPT 4.1 翻译