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: interview

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)
   else:
    if 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)

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),end = " ")
 print(*res)

# cook your dish here
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
  else:
   if 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())
 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
  else:
   if 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)



# cook your dish here
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]
  else:
   if 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

# Input data
#stdin = open("input", "r")


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")
  
  
    
   
 
  
    
    
    
  
  
  
  
  


# cook your dish here
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)

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), end=" ")
 print(*res)

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
 #Find Set LSB = (x&(-x)), isPowerOfTwo = (x & (x-1))
 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)

# cook your dish here
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()

# cook your dish here
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)
  else:
   if 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)