CF1635C.Differential Sorting

You are given an array $a$ of $n$ elements.

Your can perform the following operation no more than $n$ times: Select three indices $x,y,z$ $(1 \leq x \lt y \lt z \leq n)$ and replace $a_x$ with $a_y - a_z$. After the operation, $|a_x|$ need to be less than $10^{18}$.

Your goal is to make the resulting array non-decreasing. If there are multiple solutions, you can output any. If it is impossible to achieve, you should report it as well.

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

你最多可以执行 $n$ 次以下操作：选择三个下标 $x, y, z$（满足 $1 \leq x \lt y \lt z \leq n$），并将 $a_x$ 替换为 $a_y - a_z$。操作后需满足 $|a_x| < 10^{18}$。

你的目标是使最终得到的数组为非递减序列。若存在多种解法，输出任意一种即可；若无法实现，则也需报告该情况。

Each test contains multiple test cases. The first line will contain a single integer $t$ $(1 \leq t \leq 10000)$ — the number of test cases. Then $t$ test cases follow.

The first line of each test case contains a single integer $n$ $(3 \leq n \leq 2 \cdot 10^5)$ — the size of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots ,a_n$ $(-10^9 \leq a_i \leq 10^9)$, the elements of $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

For each test case, print $-1$ in a single line if there is no solution. Otherwise in the first line you should print a single integer $m$ $(0 \leq m \leq n)$ — number of operations you performed.

Then the $i$-th of the following $m$ lines should contain three integers $x,y,z$ $(1 \leq x \lt y \lt z \leq n)$— description of the $i$-th operation.

If there are multiple solutions, you can output any. Note that you don't have to minimize the number of operations in this task.

对于每个测试用例，若无解，则在一行中输出 $-1$。否则，第一行应输出一个整数 $m$ $(0 \leq m \leq n)$，表示你执行的操作次数。

接下来的 $m$ 行中，第 $i$ 行应包含三个整数 $x,y,z$ $(1 \leq x \lt y \lt z \leq n)$，表示第 $i$ 次操作的描述。

若存在多个解，你可以输出任意一个。注意，本题不要求最小化操作次数。

In the first example, the array becomes

$[-6,-4,2,-1,2]$ after the first operation,

$[-6,-4,-3,-1,2]$ after the second operation.

In the second example, it is impossible to make the array sorted after any sequence of operations.

In the third example, the array is already sorted, so we don't need to perform any operations.

在第一个例子中，数组在第一次操作后变为

$[-6,-4,2,-1,2]$，

在第二次操作后变为

$[-6,-4,-3,-1,2]$。

在第二个例子中，无论执行何种操作序列，都无法使数组变为有序。

在第三个例子中，数组本身已经有序，因此无需执行任何操作。