Differential Sorting(贪心/构造)

题目
题目:给定一个数组，现在可以从数组中选择下标$1<=x<y<z<=n$，令$a_x=a_y?a_z$。最多可以操作n次。询问数组是否可以变成非递减。

想法：考虑到数组本身是非递减的。其次，我们注意到前面的元素只能用后面的元素来修改，我们发现，$a_{n-1},a_n$是不能被修改到的，因此，需要满足$a_{n-1}<=a_n$。由于$a_n$决定了数组的最大值，如果$a_n$是负数，那么意味着，我们选择任意元素做为$z$，都会使$a_x$变大。所以，在数组本身不是非递减的情况，还需要满足$a_n>=0$

在满足了$a_{n-1}<=a_n,a_n>=0$这两个条件下，实际我们就可以构造了：$a_i=a_{n-1}-a_n,1<=i<=n-2$

#include
using namespace std;
#define ll long long
const int maxn = 200010;


int n, a[maxn];
void solve() { 
       
	scanf("%d", &n);
	int flag = 1;
	for (int i = 1; i <= n; ++i) { 
       
		scanf("%d", &a[i]);
		if (i > 1 && a[i] < a[i-1]) { 
       
			flag = 0;
		}
	}
	if (a[n-1] > a[n] || (a[n] < 0 && !flag)) { 
       
		printf("-1\n");
		return;
	}
	if (flag) { 
       
		printf("0\n");
		return;
	}
	printf("%d\n", n - 2);
	for (int i = 1; i <= n - 2; ++i) { 
       
		printf("%d %d %d\n", i, n - 1, n);
	}
}
int main() { 
       
	int t;
	scanf("%d", &t);
	while (t--) { 
       
		solve();
	}
}