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 < y < 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.


-----Input-----

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$.


-----Output-----

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 < y < 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.


-----Examples-----

Input
3
5
5 -4 2 -1 2
3
4 3 2
3
-3 -2 -1
Output
2
1 2 3
3 4 5
-1
0


-----Note-----

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.

Difficulty: EASY
Tags: Greedy algorithms

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if a[n - 2] > a[n - 1]:
		print(-1)
	elif a[n - 1] < 0:
		a_sorted = True
		for i in range(0, n - 1):
			if a[i] > a[i + 1]:
				a_sorted = False
		if a_sorted:
			print(0)
		else:
			print(-1)
	else:
		print(n - 2)
		for i in range(n - 2):
			print(f'{i + 1} {n - 1} {n}')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	j = n - 2
	while j >= 0 and a[j + 1] >= a[j]:
		j -= 1
	if j < 0:
		print(0)
	elif j == n - 2 or 0 > a[n - 1]:
		print(-1)
	else:
		print(j + 1)
		for k in range(1, j + 2):
			print(f'{k} {j + 2} {n}')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if a[n - 2] > a[n - 1]:
		print(-1)
		continue
	elif a[n - 1] < 0:
		if all((a[i] <= a[i + 1] for i in range(len(a) - 1))):
			print(0)
			continue
		else:
			print(-1)
	else:
		print(n - 2)
		for i in range(n - 2):
			print(f'{n - 2 - i} {n - 1} {n}')


T = int(input())
for _ in range(T):
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	b = a[::1]
	if a[n - 2] > a[n - 1]:
		print(-1)
	elif a[n - 1] < 0:
		b.sort()
		if a == b:
			print(0)
		else:
			print(-1)
	else:
		print(n - 2)
		i = 1
		while i <= n - 2:
			print(f'{i} {n - 1} {n}')
			i += 1


def is_sorted(arr):
	for i in range(1, len(arr)):
		if arr[i] < arr[i - 1]:
			return False
	return True
t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	if lst[n - 2] > lst[n - 1]:
		print(-1)
	elif lst[n - 1] < 0:
		if is_sorted(lst):
			print(0)
		else:
			print(-1)
	else:
		print(n - 2)
		for i in range(1, n - 1):
			print(str(i) + ' ' + str(n - 1) + ' ' + str(n))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l1 = a[n - 1]
	l2 = a[n - 2]
	dec = True
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			dec = False
			break
	if dec:
		print(0)
		continue
	if l2 - l1 <= l2 and l2 <= l1:
		print(n - 2)
		for i in range(n - 2):
			print(str(i + 1) + ' ' + str(n - 1) + ' ' + str(n))
		continue
	print(-1)


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	j = -1
	marker = True
	for i in range(n - 1, -1, -1):
		if a[i] >= 0:
			j = i
			break
	if j == n - 2 or j == 1 or j == 0:
		marker = False
	elif j == -1:
		for i in range(n - 1):
			if a[i] > a[i + 1]:
				marker = False
				break
		j = 1
	elif j < n - 2:
		for i in range(j - 1, n - 1):
			if a[i] > a[i + 1]:
				marker = False
				break
	if a[-2] > a[-1]:
		marker = False
	if not marker:
		print(-1)
	else:
		print(j - 1)
		for i in range(j - 1):
			print(str(i + 1) + ' ' + str(j) + ' ' + str(j + 1))


def solve(arr):
	if arr[-1] < arr[-2]:
		print(-1)
		return
	if arr[-1] < 0:
		if all((arr[i] <= arr[i + 1] for i in range(len(arr) - 1))):
			print(0)
		else:
			print(-1)
		return
	k = arr[-2] - arr[-1]
	y = len(arr) - 1
	z = len(arr)
	print(len(arr) - 2)
	for i in range(1, len(arr) - 1):
		print(i, y, z)
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	solve(arr)


t = int(input())
while t > 0:
	ans = 0
	n = int(input())
	a = list(map(int, input().split()))
	end = a[n - 1]
	high = end
	length = 1
	for i in range(n - 2, -1, -1):
		if a[i] > end:
			break
		else:
			end = a[i]
			lowIndex = i
			length += 1
	low = end
	if length == 1:
		print(-1)
	elif lowIndex == 0:
		print(0)
	elif low - high > a[lowIndex]:
		print(-1)
	else:
		print(n - length)
		for i in range(1, lowIndex + 1):
			print(i, lowIndex + 1, n)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	if a[-2] > a[-1]:
		print(-1)
	elif a[-1] >= 0:
		print(n - 2)
		for i in range(1, n - 1):
			print(i, n - 1, n)
	else:
		print([-1, 0][a == sorted(a)])


for _ in range(int(input())):
	x = int(input())
	y = list(map(int, input().split()))
	if y[-2] <= y[-1]:
		if y[-1] < 0:
			if y == sorted(y):
				print(0)
			else:
				print(-1)
		else:
			print(x - 2)
			for i in range(1, x - 1):
				print(i, x - 1, x)
	else:
		print(-1)


def isSorted(arr):
	for i in range(len(arr) - 1):
		if arr[i] > arr[i + 1]:
			return False
	return True
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if n <= 1:
		print(0)
	elif arr[-2] > arr[-1]:
		print(-1)
	elif isSorted(arr):
		print(0)
	elif arr[-1] < 0:
		print(-1)
	else:
		print(n - 2)
		for i in range(1, n - 1):
			print(i, n - 1, n)


for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	(l1, l2) = (arr[N - 1], arr[N - 2])
	dec = True
	for i in range(N - 1):
		if arr[i] > arr[i + 1]:
			dec = False
			break
	if dec:
		print(0)
	elif l2 - l1 <= l2 and l2 <= l1:
		print(N - 2)
		for i in range(N - 2):
			print(i + 1, N - 1, N)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	spic = list(map(int, input().split()))
	if spic[n - 2] > spic[n - 1]:
		print(-1)
		continue
	if spic[n - 1] < 0:
		if spic == sorted(spic):
			print(0)
		else:
			print(-1)
		continue
	print(n - 2)
	for i in range(1, n - 1):
		print(i, n - 1, n)


def solve():
	n = int(input())
	ll = list(map(int, input().split()))
	if ll[n - 2] > ll[-1]:
		print(-1)
	elif ll[-1] < 0:
		if ll == sorted(ll):
			print(0)
		else:
			print(-1)
	else:
		print(n - 2)
		for i in range(n - 2):
			print(i + 1, n - 1, n)
t = int(input())
while t:
	res = solve()
	t -= 1


import sys
input = sys.stdin.readline
for _ in [0] * int(input()):
	n = int(input())
	a = list(map(int, input().split()))
	x = a[-1]
	y = a[-2]
	if y > x:
		print(-1)
	elif x >= 0:
		print(n - 2)
		for i in range(1, n - 1, 1):
			print(i, n - 1, n)
	elif a == sorted(a):
		print(0)
	else:
		print(-1)


I = input
for _ in range(int(I())):
	n = int(I())
	lst = list(map(int, I().split()))
	(y, z) = (n - 1, n)
	diff = lst[y - 1] - lst[z - 1]
	if diff > 0:
		print(-1)
	elif lst[z - 1] < 0:
		if lst == sorted(lst):
			print(0)
		else:
			print(-1)
	else:
		print(n - 2)
		for x in range(n - 2, 0, -1):
			print(x, y, z)


import math, bisect
from sys import stdin
input = stdin.readline

def solve(n, a):
	x = a[n - 1]
	y = a[n - 2]
	b = 1
	for i in range(0, n - 1):
		if a[i] > a[i + 1]:
			b = 0
			break
	if b == 1:
		print(0)
		return
	if y - x <= y and y <= x:
		print(n - 2)
		for i in range(0, n - 2):
			print(i + 1, n - 1, n)
		return
	print(-1)
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	solve(n, a)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if l[-2] > l[-1]:
		print(-1)
	elif l[-2] < 0 and l[-1] < 0:
		ans = True
		for j in range(n - 2, -1, -1):
			if l[j] > l[j + 1]:
				ans = False
				break
		if ans:
			print(0)
		else:
			print(-1)
	else:
		print(n - 2)
		for j in range(n - 2):
			print(j + 1, n - 1, n)


def fun(a):
	n = len(a)
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			return False
	return True
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	if a[-1] < 0 and a[-2] < 0:
		if fun(a):
			print(0)
		else:
			print(-1)
	elif a[-1] >= a[-2]:
		print(n - 2)
		for x in range(n - 2):
			print(x + 1, n - 1, n)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split(' ')]
	isSorted = True
	for i in range(1, n):
		if arr[i] < arr[i - 1]:
			isSorted = False
			break
	if isSorted:
		print(0)
	elif arr[-2] <= arr[-1] and arr[-2] - arr[-1] <= arr[-2] and (arr[-2] - arr[-1] <= arr[-1]):
		print(n - 2)
		for i in range(1, n - 1):
			print(i, n - 1, n)
	else:
		print(-1)


import math

def modFact(n, p):
	if n >= p:
		return 0
	result = 1
	for i in range(1, n + 1):
		result = result * i % p
	return result

def input_int():
	return int(input())

def input_multiple():
	return map(int, input().split())
t = input_int()
while t > 0:
	n = input_int()
	a = list(input_multiple())
	if a[-2] > a[-1]:
		print(-1)
	else:
		flag = True
		for i in range(n - 1):
			if a[i] > a[i + 1]:
				flag = False
				break
		if flag:
			print(0)
		elif a[n - 2] >= a[n - 2] - a[n - 1]:
			print(n - 2)
			for i in range(1, n - 1):
				print(i, n - 1, n)
		else:
			print(-1)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if arr[n - 2] > arr[n - 1]:
		print(-1)
	elif arr[n - 1] < 0:
		temp = arr[:]
		temp.sort()
		if temp == arr:
			print(0)
		else:
			print(-1)
	else:
		print(n - 2)
		for i in range(n - 2):
			print(i + 1, n - 1, n)


def check(l):
	k = l[0]
	for ele in l:
		if ele >= k:
			k = ele
		else:
			return False
	return True
for _ in range(int(input())):
	bool = True
	n = int(input())
	l = list(map(int, input().split()))
	if check(l):
		print(0)
	elif l[-1] < l[-2]:
		print(-1)
	elif l[-1] < 0 and l[-2] < 0:
		print(-1)
	else:
		print(n - 2)
		for i in range(n - 2):
			print(i + 1, n - 1, n)


t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if a[n - 2] > a[n - 1]:
		print(-1)
		continue
	if a[n - 1] < 0:
		flag = 1
		for i in range(1, n):
			if a[i - 1] > a[i]:
				flag = 0
				break
		if flag == 1:
			print(0)
			continue
		else:
			print(-1)
			continue
	print(n - 2)
	for i in range(n - 3, -1, -1):
		print(i + 1, n - 1, n)


import sys
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().strip().split()]
	check = True
	for i in range(1, n):
		if a[i] < a[i - 1]:
			check = False
			break
	if check:
		print(0)
	elif a[-1] < a[-2] or a[-1] < 0:
		print(-1)
	else:
		print(n - 2)
		for i in range(n - 2):
			print(i + 1, n - 1, n)


for k in range(int(input())):
	ab = int(input())
	abc = list(map(int, input().split()))
	count = 0
	if abc[-2] > abc[-1]:
		print(-1)
	elif abc[-1] >= 0:
		print(ab - 2)
		for i in range(ab - 2):
			print(i + 1, ab - 1, ab)
	elif abc == sorted(abc):
		print(0)
	else:
		print(-1)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if l[-2] > l[-1]:
		print(-1)
	elif l[-1] < 0:
		if l == sorted(l):
			print(0)
		else:
			print(-1)
	else:
		x = len(l) - 2
		print(x)
		for i in range(n - 2):
			print(i + 1, n - 1, n)


import sys
import math
from collections import deque, defaultdict
input = sys.stdin.readline

def multiple():
	a = map(int, input().split())
	return a

def array():
	a = input().split()
	return a

def intarray():
	a = list(map(int, input().split()))
	return a

def nondec(a):
	n = len(a)
	if n == 1:
		return True
	for i in range(1, n):
		if a[i] >= a[i - 1]:
			continue
		else:
			return False
	return True

def solution():
	n = int(input())
	a = intarray()
	if nondec(a):
		print(0)
		return
	if a[n - 2] > a[n - 1] or a[n - 2] - a[n - 1] > a[n - 2]:
		print(-1)
		return
	print(n - 2)
	for i in range(n - 2):
		print(i + 1, n - 1, n)
	return
t = int(input())
for _ in range(t):
	solution()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	l1 = arr[n - 1]
	l2 = arr[n - 2]
	flag = True
	for i in range(n - 1):
		if arr[i] > arr[i + 1]:
			flag = False
			break
	if flag:
		print(0)
		continue
	if l2 - l1 <= l2 and l2 <= l1:
		print(n - 2)
		for i in range(n - 2):
			print(i + 1, n - 1, n)
		continue
	print(-1)


for t in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	sm = 0
	res = list()
	if ls[n - 1] < ls[n - 2]:
		print(-1)
		continue
	flag = 0
	for i in range(n - 1):
		if ls[i] > ls[i + 1]:
			flag = 1
			break
	if flag:
		if ls[n - 2] - ls[n - 1] <= ls[n - 2]:
			print(n - 2)
			for i in range(1, n - 1):
				print(i, n - 1, n)
		else:
			print(-1)
	else:
		print(0)


import sys
import math
strInp = lambda : input().strip().split()
intInp = lambda : list(map(int, strInp()))

def isSorted(arr):
	for i in range(len(arr) - 1):
		if arr[i] > arr[i + 1]:
			return False
			break
	return True
for t in range(int(input())):
	n = int(input())
	arr = intInp()
	if isSorted(arr):
		print(0)
	elif arr[len(arr) - 1] < 0 or arr[len(arr) - 2] > arr[len(arr) - 1]:
		print(-1)
	else:
		print(n - 2)
		for i in range(n - 2):
			print(i + 1, n - 1, n)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	found = True
	for i in range(1, n):
		if arr[i] < arr[i - 1]:
			found = False
			break
	if found:
		print(0)
	elif arr[-1] < 0 or arr[-2] > arr[-1]:
		print(-1)
	else:
		print(n - 2)
		for i in range(n - 2):
			print(i + 1, n - 1, n)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	i = n - 2
	while i >= 0 and a[i] <= a[i + 1]:
		i -= 1
	if i == n - 2 or (i >= 0 and a[-1] < 0):
		print(-1)
		continue
	print(i + 1)
	j = i
	while j >= 0:
		print(j + 1, i + 2, n)
		j -= 1


import math
t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	check = True
	for i in range(n - 1):
		if arr[i] > arr[i + 1]:
			check = False
			break
	if check:
		print(0)
		continue
	if arr[-1] < 0:
		print(-1)
		continue
	elif arr[-2] > arr[-1]:
		print(-1)
		continue
	m = n - 2
	print(m)
	for i in range(1, m + 1):
		print(i, n - 2 + 1, n - 1 + 1)


def incr(a, n):
	var = True
	for j in range(n - 1):
		if a[j] > a[j + 1]:
			var = False
			return var
	return var
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if a[n - 2] > a[n - 1]:
		print(-1)
	elif a[n - 1] < 0:
		if incr(a, n) == True:
			print(0)
		else:
			print(-1)
	else:
		print(n - 2)
		for j in range(n - 2):
			print(j + 1, n - 1, n)


for i in range(int(input())):
	length = int(input())
	full_list = list(map(int, input().split()))
	if full_list[-2] > full_list[-1]:
		print(-1)
	elif full_list[-1] >= 0:
		changes = [*map(lambda x: x + 1, list(range(0, length - 2)))]
		print(len(changes))
		for x in changes:
			print(x, length - 1, length)
	else:
		newlist = sorted(full_list)
		if newlist == full_list:
			print(0)
		else:
			print(-1)


def solve(n, arr):
	if arr[-1] < arr[-2]:
		print(-1)
		return
	diff = arr[-2] - arr[-1]
	if diff <= arr[-2]:
		print(n - 2)
		for i in range(n - 2):
			print(i + 1, n - 1, n)
			arr[i] = arr[-2] - arr[-1]
		return
	pos = n - 1
	res = []
	for i in range(n - 2, 0, -1):
		if arr[i] < arr[i - 1]:
			if arr[pos] < 0:
				print(-1)
				return
			else:
				arr[i - 1] = arr[i] - arr[pos]
				res.append([i, i + 1, pos])
		if arr[i] > arr[pos]:
			pos = i
	print(len(res))
	for row in res:
		print(''.join([str(s) for s in row]))
	return

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		solve(n, arr)
main()


from math import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from collections import Counter as ctr
from collections import deque as dq
from array import array
inp = lambda : int(input())
li = lambda : list(map(int, input().split()))
lb = lambda : list(map(int, input()))
ls = lambda : list(input())
bi = lambda n: bin(n).replace('0b', '')
yn = lambda f: print('NYOE S'[f::2])

def solve(__=1):
	for _ in range(__):
		n = inp()
		a = li()
		if a[-2] > a[-1]:
			print(-1)
			continue
		b = sorted(a)
		if a == b:
			print(0)
		elif a[-1] < 0:
			print(-1)
		else:
			print(n - 2)
			for i in range(1, n - 1):
				print(i, n - 1, n)
solve(inp())


import sys
t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	a = [int(x) for x in sys.stdin.readline().split()]
	if a[-2] > a[-1]:
		print(-1)
		continue
	if a[-1] >= 0:
		print(n - 2)
		for q in range(0, n - 2):
			print(q + 1, n - 1, n)
		continue
	flag = 1
	for i in range(0, n - 1):
		if a[i] > a[i + 1]:
			flag = 0
			break
	print(flag - 1)


import sys

def r():
	return map(int, next(sys.stdin).split())
for _ in range(int(input())):
	N = next(r())
	l = [*r()]
	if l[-2] > l[-1]:
		print(-1)
		continue
	if l[-1] >= 0:
		print(N - 2)
		for i in range(N - 2):
			print(i + 1, N - 1, N)
	else:
		for i in range(N - 1):
			if l[i] > l[i + 1]:
				print(-1)
				break
		else:
			print(0)


t = int(input())
while t:
	n = int(input())
	l1 = list(map(int, input().split(' ')))
	count = 0
	if l1[len(l1) - 2] > l1[len(l1) - 1]:
		print(-1)
	elif l1[len(l1) - 1] >= 0:
		print(len(l1) - 2)
		for i in range(0, len(l1) - 2):
			print(i + 1, len(l1) - 1, len(l1))
	else:
		flag = 0
		for i in range(0, len(l1) - 1):
			if l1[i] > l1[i + 1]:
				print(-1)
				flag = 1
				break
		if flag == 0:
			print(0)
	t = t - 1


def sorted(nums):
	for i in range(len(nums) - 1):
		if nums[i] > nums[i + 1]:
			return False
	return True
testcases = int(input())
for i in range(testcases):
	n = int(input())
	a = list(map(int, input().split()))
	if a[-2] > a[-1]:
		print('-1')
	elif a[-1] < 0:
		if sorted(a):
			print('0')
		else:
			print('-1')
	else:
		print(n - 2)
		for i in range(1, n - 1):
			print(i, n - 1, n)


import sys

def input():
	return sys.stdin.readline()[:-1]

def readline():
	return map(int, input().split())

def solve():
	(n,) = readline()
	a = list(readline())
	operations = list()
	(x, y, z) = a[-3:]
	if y > z:
		return None
	if z >= 0:
		return [(i, n - 1, n) for i in range(1, n - 1)]
	if all((u <= v for (u, v) in zip(a, a[1:]))):
		return []
	return None
t = int(input())
for __ in range(t):
	operations = solve()
	if operations is None:
		print(-1)
	else:
		print(len(operations))
		for op in operations:
			print(*op)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.insert(0, 0)
	if a[n - 1] > a[n]:
		print('-1')
		continue
	flag = False
	res = 0
	for i in range(n - 2, 0, -1):
		tmp = a[i + 1] - a[n]
		if a[i] > a[i + 1] and tmp > a[i + 1]:
			print('-1')
			flag = True
			break
		if tmp <= a[i + 1]:
			res = i
			break
	if flag:
		continue
	print(res)
	for i in range(res):
		print(i + 1, res + 1, n)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if sorted(a) == a:
		print(0)
	elif a[-1] < a[-2] or a[-1] < 0:
		print(-1)
	else:
		cnt = n - 2
		print(cnt)
		for i in range(1, n - 1):
			print(i, n - 1, n)


def main():
	n = int(input())
	arr = list(map(int, input().split()))
	arr_c = arr.copy()
	arr_c.sort()
	if arr_c == arr:
		print(0)
		return
	if arr[-1] < arr[-2]:
		print(-1)
		return
	if arr[-1] >= 0:
		print(n - 2)
		for i in range(1, n - 1):
			print(i, n - 1, n)
		return
	print(-1)
	return
for _ in range(int(input())):
	main()


tt = int(input())
for i in range(tt):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	temp = 0
	if sorted(l) == l:
		print(0)
	elif l[n - 2] > l[n - 1]:
		print(-1)
	else:
		last = l[n - 1]
		if last >= 0:
			print(n - 2)
			for j in range(1, n - 1):
				print(j, n - 1, n)
		elif sorted(l) == l:
			print(0)
		else:
			print(-1)


T = int(input())
for t in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	if sorted(a) == a:
		print(0)
		continue
	if a[n - 2] > a[n - 1] or a[n - 1] < 0:
		print(-1)
		continue
	sol = []
	print(n - 2)
	for i in range(n - 2):
		print(i + 1, n - 1, n)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if a == sorted(a):
		print(0)
		continue
	if a[-1] < 0 or a[-1] < a[-2]:
		print(-1)
		continue
	print(n - 2)
	for i in range(n - 2):
		print(i + 1, n - 1, n)


t = int(input())
arr = []
for _ in range(t):
	n = int(input())
	temp = list(map(int, input().split()))
	arr.append(temp)
for temp in arr:
	n = len(temp)
	if temp[-1] < temp[-2]:
		print(-1)
	elif temp[-1] < 0:
		if temp == sorted(temp):
			print(0)
		else:
			print(-1)
	else:
		print(len(temp) - 2)
		for i in range(1, n - 1):
			print(i, n - 1, n, sep=' ')


t = int(input())
while t != 0:
	n = int(input())
	a = list(map(int, input().split()))
	if a[-2] > a[-1]:
		print(-1)
		t -= 1
		continue
	ok = 1
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			ok = 0
			break
	if ok:
		print(0)
	elif a[n - 2] - a[n - 1] <= a[n - 2]:
		print(n - 2)
		for i in range(n - 3, -1, -1):
			a[i] = a[n - 2] - a[n - 1]
			print(i + 1, n - 1, n)
	else:
		print(-1)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	if nums == sorted(nums):
		print(0)
	elif nums[-2] > nums[-1] or (nums[-1] < 0 and nums != sorted(nums)):
		print(-1)
	else:
		print(n - 2)
		for i in range(len(nums) - 2):
			print(i + 1, n - 1, n)


import math
for i in range(int(input())):
	n = int(input())
	A = [int(k) for k in input().split()]
	if A == sorted(A):
		print(0)
	elif A[-2] <= A[-1] and A[-2] - A[-1] <= A[-2]:
		print(n - 2)
		for k in range(0, n - 2):
			print(k + 1, n - 1, n)
	else:
		print(-1)


T = int(input())
for t in range(0, T):
	n = int(input())
	a = list(map(int, input().split()))
	flag = 0
	for i in range(0, n - 1):
		if a[i + 1] < a[i]:
			flag = 1
	if flag == 0:
		print(0)
	elif a[n - 2] > a[n - 1]:
		print(-1)
	elif a[n - 2] < 0 and a[n - 1] < 0:
		print(-1)
	else:
		print(n - 2)
		for i in range(0, n - 2):
			print(i + 1, n - 1, n)


import math
from collections import *

def solve():
	n = int(input())
	a = [int(i) for i in input().split()]
	if a == sorted(a):
		print(0)
		return
	if a[n - 2] > a[n - 1]:
		print(-1)
	elif a[n - 1] < 0:
		print(-1)
	else:
		print(n - 2)
		for i in range(n - 2):
			print(i + 1, n - 1, n, end='\n')
t = int(input())
for _ in range(t):
	solve()


from collections import Counter
from collections import defaultdict
import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	if arr[-1] < arr[-2]:
		print(-1)
	elif arr == sorted(arr):
		print(0)
	else:
		m = arr[-1]
		if m >= 0:
			print(n - 2)
			for i in range(n - 3, -1, -1):
				print(i + 1, n - 1, n)
		else:
			flag = 0
			prev = math.inf
			ind = -1
			for i in range(n - 1, -1, -1):
				if arr[i] > prev:
					flag = 1
					break
				prev = arr[i]
				if prev >= 0:
					ind = i + 1
					break
			if flag == 1:
				print(-1)
			elif ind < 3:
				print(-1)
			elif arr[ind - 1] < arr[ind - 2]:
				print(-1)
			else:
				print(ind - 2)
				for i in range(ind - 3, -1, -1):
					print(i + 1, ind - 1, ind)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if arr == sorted(arr):
		print(0)
		continue
	if arr[-1] < 0 or arr[-1] < arr[-2]:
		print(-1)
		continue
	print(n - 2)
	for j in range(n - 2):
		print(j + 1, n - 1, n)


out = []
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	if a == sorted(a):
		print(0)
		continue
	if a[-1] < 0 or a[-1] < a[-2]:
		print(-1)
		continue
	t = a[-2] - a[-1]
	print(n - 2)
	for i in range(n - 2):
		print(i + 1, n - 1, n)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = a.copy()
	b.sort()
	if b == a:
		print(0)
	elif a[-1] < a[-2] or a[-1] < 0 or (a[-2] <= -1000000000 and a[-1] >= 1000000000):
		print(-1)
	else:
		print(n - 2)
		for i in range(n - 2):
			print(i + 1, n - 1, n)


import math
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	if a == sorted(a):
		print(0)
		continue
	id = 0
	for i in range(n - 1, 0, -1):
		if a[i - 1] > a[i]:
			id = i
			break
	mx = a[id] - a[-1]
	while mx == -10 ** 18:
		id = id + 1
		mx = a[id] - a[-1]
	if id == n - 1:
		print(-1)
		continue
	if mx > a[id]:
		print(-1)
	else:
		print(id)
		if id != 0:
			for i in range(id):
				print(i + 1, id + 1, n)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007
t = inp()
for j in range(t):
	n = inp()
	l = seq()
	if l[-1] < l[-2]:
		print(-1)
		continue
	if sorted(l) == l:
		print(0)
		continue
	if l[n - 1] < 0:
		print(-1)
		continue
	cal = l[-1] - l[-2]
	print(n - 2)
	for i in range(n - 2):
		l[i] = cal
		print(i + 1, n - 1, n)


from collections import Counter
from collections import defaultdict
import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	if arr[-1] < arr[-2]:
		print(-1)
	elif arr == sorted(arr):
		print(0)
	else:
		m = arr[-1]
		if m >= 0:
			print(n - 2)
			for i in range(n - 3, -1, -1):
				print(i + 1, n - 1, n)
		else:
			print(-1)


def AbhiSolveKiya(n, a):
	if sorted(a) == a:
		print(0)
		return
	if a[-2] > a[-1]:
		print(-1)
		return
	yz = a[-2] - a[-1]
	if yz > a[-2]:
		print(-1)
		return
	for i in range(n - 2):
		a[i] = yz
	if sorted(a) != a:
		print(-1)
		return
	print(n - 2)
	for i in range(n - 2):
		print(i + 1, n - 1, n)
	return
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	AbhiSolveKiya(n, a)


N = int(input())
inputs = []
for i in range(N):
	elm = int(input())
	arr = list(map(int, input().split()))
	inputs.append(arr)
ans = []
for arr in inputs:
	(last1, last2) = (arr[-1], arr[-2])
	check = True
	for i in range(len(arr) - 1):
		if arr[i] > arr[i + 1]:
			check = False
			break
	if check:
		print(0)
		continue
	else:
		if last2 - last1 <= last2 and last2 <= last1:
			print(len(arr) - 2)
			for i in range(len(arr) - 2):
				print(i + 1, end=' ')
				print(len(arr) - 1, end=' ')
				print(len(arr))
			continue
		print(-1)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if l[n - 1] < l[n - 2]:
		print(-1)
	elif l[n - 1] < 0:
		if l == sorted(l):
			print(0)
		else:
			print(-1)
	else:
		print(n - 2)
		for k in range(1, n - 1):
			print(k, n - 1, n, end=' ')
			print()


import sys

def main():
	a = int(sys.stdin.readline())
	for _ in range(a):
		f = int(sys.stdin.readline())
		x = list(map(int, sys.stdin.readline().split()))
		if sorted(x) == x:
			print(0)
		elif x[-1] < x[-2] or x[-1] < 0:
			print(-1)
		else:
			print(f - 2)
			for i in range(f - 2):
				print(i + 1, f - 1, f)
				x[i] = x[-2] - x[-1]
main()


import sys
input = sys.stdin.readline

def solve(n, arr):
	if arr[-2] > arr[-1]:
		print(-1)
		return
	ans = []
	ops = 0
	if arr[-1] >= 0 and arr[-2] <= arr[-1]:
		for i in range(n - 3, -1, -1):
			if arr[i] == arr[-2] - arr[-1]:
				continue
			arr[i] = arr[-2] - arr[-1]
			ops += 1
			ans.append((i + 1, n - 1, n))
	else:
		for i in range(n - 3, -1, -1):
			if arr[i] > arr[i + 1]:
				print(-1)
				return
	print(ops)
	for (a, b, c) in ans:
		print(a, b, c)
for j in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	solve(n, arr)


t = int(input())
for i in range(0, t):
	n = int(input())
	a = []
	a = list(map(int, input().split()))
	arr = sorted(a)
	flag = 0
	for j in range(0, n):
		if arr[j] != a[j]:
			flag = 1
	if flag == 0:
		print(0)
	elif n == 1:
		print(0)
	elif a[n - 1] >= a[n - 2] and a[n - 1] >= 0:
		print(n - 2)
		for i in range(0, n - 2):
			print(i + 1, n - 1, n)
	elif a[n - 1] >= a[n - 2] and a[n - 1] < 0:
		print(-1)
	else:
		print(-1)


t = int(input())

def isSorted(a):
	for i in range(len(a) - 1):
		if a[i + 1] < a[i]:
			return False
	return True
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	if arr[n - 2] > arr[n - 1]:
		print('-1')
		continue
	if arr[n - 1] >= 0:
		m = 0
		a = []
		for idx in range(len(arr)):
			if idx == len(arr) - 2:
				break
			else:
				arr[idx] = arr[n - 2] - arr[n - 1]
				m += 1
				a.append([str(idx + 1), str(n - 1), str(n)])
		print(str(m))
		for j in a:
			print(' '.join(j))
	elif isSorted(arr):
		print('0')
	else:
		print('-1')


for iii in range(int(input())):
	n = int(input())
	q = list(map(int, input().split()))
	if q[n - 2] > q[n - 1]:
		print(-1)
		continue
	q1 = [i for i in q]
	q1.sort()
	if q == q1:
		print(0)
		continue
	if q[n - 1] < 0:
		print(-1)
		continue
	cou = 0
	q2 = []
	x = q[n - 2] - q[n - 1]
	for i in range(n - 2):
		if q[i] != x:
			cou += 1
			q2.append(i + 1)
	print(cou)
	for i in q2:
		print(i, n - 1, n)