You are given a sequence $A_1, A_2, \ldots, A_N$. You should select a (not necessarily contiguous) subsequence of $A$ and reverse it. In other words, if you select a subsequence $A_{i_1}, A_{i_2}, \ldots, A_{i_K}$ ($1 \le i_1 < \ldots < i_K \le N$), then for each valid $j$, the $i_j$-th element of the resulting sequence is equal to the $i_{K+1-j}$-th element of the original sequence; all other elements are the same as in the original sequence.
In the resulting sequence, you want to calculate the maximum sum of a contiguous subsequence (possibly an empty sequence, with sum $0$). Find its maximum possible value and a subsequence which you should select in order to obtain this maximum value. If there are multiple solutions, you may find any one of them.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print two lines.
- The first of these lines should contain a single integer ― the maximum possible sum of a contiguous subsequence.
- The second line should contain an integer $K$ followed by a space and $K$ space-separated integers $i_1, i_2, \ldots, i_K$.

-----Constraints-----
- $1 \le T \le 2,000$
- $2 \le N \le 10^5$
- $|A_i| \le 10^9$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $2 \cdot 10^6$

-----Example Input-----
2
5
-4 2 -4 3 -5
3
-3 -2 -1

-----Example Output-----
5
2 2 3
0
0

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	count = 0
	for i in a:
		if i > 0:
			ans += i
			count += 1
	res = []
	for i in range(count):
		if a[i] <= 0:
			res.append(i + 1)
	for i in range(count, n):
		if a[i] > 0:
			res.append(i + 1)
	print(ans)
	print(len(res), *res)


def count(a):
	x = 0
	for i in a:
		if i > 0:
			x = x + 1
	return x
for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	su = 0
	c = []
	d = []
	for i in a:
		if i > 0:
			su = su + i
	if su == 0:
		print(0)
		print(0)
	else:
		y = count(a)
		for i in range(len(a)):
			if i + 1 <= y:
				if a[i] < 0:
					c.append(i + 1)
			elif a[i] > 0:
				d.append(i + 1)
		for i in range(abs(len(d) - len(c))):
			d.pop(0)
		print(su)
		print(len(c + d), *c + d, end=' ')


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	tp = 0
	s = 0
	for i in range(n):
		if a[i] > 0:
			tp += 1
			s += a[i]
	ans = []
	for i in range(tp):
		if a[i] <= 0:
			ans.append(i + 1)
	for i in range(tp, n):
		if a[i] > 0:
			ans.append(i + 1)
	print(s)
	print(len(ans), *ans)


import sys

def revsubseq(lis):
	s = 0
	e = n - 1
	nls = []
	while e > s:
		if lis[s] > 0 and lis[e] <= 0:
			(lis[s], lis[e]) = (lis[e], lis[s])
			nls.append(s + 1)
			nls.append(e + 1)
			s += 1
			e -= 1
		elif lis[s] <= 0 and lis[e] > 0:
			s += 1
			e -= 1
		elif lis[s] <= 0 and lis[e] <= 0:
			s += 1
		elif lis[s] > 0 and lis[e] > 0:
			e -= 1
	return nls

def mxsubarray(lis):
	globalmax = lis[0]
	curmax = lis[0]
	for i in range(1, n):
		curmax = max(curmax + lis[i], lis[i])
		globalmax = max(globalmax, curmax)
	return globalmax
for t in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	nls = revsubseq(lis)
	mx = mxsubarray(lis)
	if mx < 0:
		print(0)
		print(0)
	else:
		print(mx)
		print(len(nls), end=' ')
		print(*nls)


test = int(input())
for _ in range(test):
	n = int(input())
	arr = list(map(int, input().split()))
	pos = 0
	num = 0
	temp = []
	for ii in arr:
		if ii >= 0:
			pos += ii
			num += 1
	p = 0
	n = 0
	for i in range(len(arr)):
		if i < num:
			if arr[i] < 0:
				temp.append(i + 1)
				n += 1
		elif arr[i] >= 0:
			temp.append(i + 1)
			p += 1
	print(pos)
	if p == n:
		k = [len(temp)]
		k.extend(temp)
		print(*k)
	else:
		print(0)


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	(sum1, ctr, arr) = (0, 0, [])
	for i in range(n):
		if lst[i] > 0:
			ctr += 1
	for i in range(n):
		if i < ctr:
			if lst[i] < 0:
				arr.append(i + 1)
			elif lst[i] > 0:
				sum1 += lst[i]
		elif lst[i] > 0:
			arr.append(i + 1)
			sum1 += lst[i]
	print(sum1)
	print(len(arr), ' '.join(list(map(str, arr))))


from sys import stdin
from math import ceil, gcd
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	count_pos = 0
	ans = 0
	for i in range(n):
		if arr[i] >= 0:
			count_pos += 1
			ans += arr[i]
	case = []
	for i in range(count_pos):
		if arr[i] < 0:
			case.append(i + 1)
	for i in range(count_pos, n):
		if arr[i] >= 0:
			case.append(i + 1)
	print(ans)
	if len(case) == 0:
		print(0)
	else:
		print(len(case), end=' ')
		print(*case)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	p = 0
	for i in range(len(l)):
		if l[i] >= 0:
			p += 1
			ans += l[i]
	seq = []
	for i in range(len(l)):
		if i < p and l[i] < 0:
			seq.append(i + 1)
		elif i >= p and l[i] > 0:
			seq.append(i + 1)
	print(ans)
	print(len(seq), end=' ')
	for i in seq:
		print(i, end=' ')
	print()


a = int(input())
for j in range(0, a):
	b = int(input())
	l1 = list(map(int, input().split(' ')))
	l2 = []
	sum = 0
	first = 0
	count = 0
	last = len(l1) - 1
	while first <= last:
		temp = 0
		if l1[first] < 0:
			count += 1
			if l1[last] > 0:
				sum = sum + l1[last]
				temp = l1[first]
				l1[first] = l1[last]
				l1[last] = temp
				l2.append(first + 1)
				l2.append(last + 1)
				first += 1
				last -= 1
			else:
				last -= 1
		else:
			x = l1[first]
			sum = sum + l1[first]
			first += 1
	l2.sort()
	if count > 0:
		if len(l2) == 0:
			print('0')
			print(len(l2))
		else:
			print(sum)
			print(len(l2), end=' ')
		if len(l2) == 0:
			pass
		else:
			for k in range(0, len(l2)):
				if k == len(l2) - 1:
					print(l2[k])
				else:
					print(l2[k], end=' ')
	else:
		print(sum)
		print('0')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	t_sum = 0
	count = 0
	for i in range(n):
		if l[i] >= 0:
			t_sum += l[i]
			count += 1
	print(t_sum)
	if count == n or count == 0:
		print(0)
	else:
		index_1 = []
		index_2 = []
		i = 0
		j = len(l) - 1
		while i < j:
			while i < n and l[i] < 0:
				i += 1
			while j > -1 and l[j] > 0:
				j -= 1
			if i < j:
				index_1.append(i + 1)
				index_2.append(j + 1)
				i += 1
				j -= 1
		index_2.reverse()
		print(len(index_1) + len(index_2), *index_1, *index_2)


def solve():
	n = int(input())
	l = list(map(int, input().split()))
	s = 0
	p = 0
	for i in l:
		if i >= 0:
			p += 1
			s += i
	if p == 0:
		return [0, []]
	ans = []
	for i in range(0, p):
		if l[i] < 0:
			ans.append(i + 1)
	for i in range(p, n):
		if l[i] >= 0:
			ans.append(i + 1)
	return [s, ans]
for _ in range(int(input())):
	p = solve()
	print(p[0])
	p1 = [len(p[1])] + p[1]
	print(*p1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	first = 0
	last = n - 1
	sseq = []
	while first < last:
		if a[last] > 0:
			while first < last:
				if a[first] < 0:
					p = a[first]
					q = a[last]
					a[first] = q
					a[last] = p
					sseq.append(first + 1)
					sseq.append(last + 1)
					first += 1
					break
				first += 1
		last -= 1
	sseq.sort()
	summ = 0
	for i in range(n):
		if a[i] >= 0:
			summ += a[i]
		else:
			break
	print(summ)
	print(len(sseq), *sseq)


try:
	import sys
	from sys import stdin
	import math

	def iinput():
		return int(input())

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

	def linput():
		return list(map(int, input().split()))

	def fiinput():
		return int(stdin.readline())

	def fminput():
		return map(int, stdin.readline().strip().split())

	def flinput():
		return list(map(int, stdin.readline().strip().split()))
	for _ in range(iinput()):
		n = iinput()
		list1 = linput()
		c = 0
		s = 0
		for i in range(n):
			if list1[i] > 0:
				c += 1
				s += list1[i]
		list2 = []
		for i in range(c):
			if list1[i] <= 0:
				list2.append(i + 1)
		for i in range(c, n):
			if list1[i] > 0:
				list2.append(i + 1)
		print(s)
		print(len(list2), *list2)
except:
	pass


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	(noOfPositive, noOfNegative, ans) = (0, 0, 0)
	for i in a:
		if i > 0:
			ans += i
			noOfPositive += 1
	ansList = []
	for i in range(noOfPositive):
		if a[i] <= 0:
			ansList.append(i + 1)
			noOfNegative += 1
	pList = []
	for i in range(n - 1, -1, -1):
		if noOfNegative == 0:
			break
		elif a[i] > 0:
			noOfNegative -= 1
			pList.append(i + 1)
	pList = reversed(pList)
	ansList += pList
	print(ans)
	print(len(ansList), *ansList)


for _ in range(int(input())):
	n = int(input())
	(seq, ind) = (list(map(int, input().split())), [])
	seq.insert(0, 0)
	(count, sum_) = (0, 0)
	for i in range(1, n + 1):
		if seq[i] >= 0:
			count += 1
			sum_ += seq[i]
	for i in range(1, count + 1):
		if seq[i] < 0:
			ind.append(i)
	for i in range(count + 1, n + 1):
		if seq[i] >= 0:
			ind.append(i)
	print(sum_)
	print(len(ind), end=' ')
	for i in ind:
		print(i, end=' ')
	print()


for tc in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	p = 0
	ans = 0
	x = []
	for i in range(n):
		if arr[i] >= 0:
			p += 1
			ans += arr[i]
	for i in range(p):
		if arr[i] < 0:
			x.append(i + 1)
	for i in range(p, n):
		if arr[i] >= 0:
			x.append(i + 1)
	print(ans)
	print(len(x), end=' ')
	for i in x:
		print(i, end=' ')
	print()


t = int(input())
while t:
	t = t - 1
	n = int(input())
	A = list(map(int, input().split()))
	z = 0
	sum = 0
	for x in A:
		if x > 0:
			sum += x
			z += 1
	V = A[:z]
	index = []
	for i in range(1, len(A) + 1):
		if i <= z:
			if A[i - 1] < 0:
				index.append(i)
		elif A[i - 1] > 0:
			index.append(i)
	if sum == 0:
		print(0)
		print(0)
	else:
		print(sum)
		print(len(index), end=' ')
		for x in index:
			print(x, end=' ')
		print()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.insert(0, 9)
	ans = m = 0
	for i in range(1, n + 1):
		if arr[i] >= 0:
			m += 1
			ans += arr[i]
	sub = []
	for i in range(1, m + 1):
		if arr[i] < 0:
			sub.append(i)
	for i in range(m + 1, n + 1):
		if arr[i] >= 0:
			sub.append(i)
	if ans == 0:
		print(ans)
		print(ans)
	else:
		print(ans)
		print(len(sub), *sub)