You have an integer sequence of length N: a_1, a_2, ..., a_N.
You repeatedly perform the following operation until the length of the sequence becomes 1:
 - First, choose an element of the sequence.
 - If that element is at either end of the sequence, delete the element.
 - If that element is not at either end of the sequence, replace the element with the sum of the two elements that are adjacent to it. Then, delete those two elements.
You would like to maximize the final element that remains in the sequence.
Find the maximum possible value of the final element, and the way to achieve it.

-----Constraints-----
 - All input values are integers.
 - 2 \leq N \leq 1000
 - |a_i| \leq 10^9

-----Input-----
Input is given from Standard Input in the following format:
N
a_1 a_2 ... a_N

-----Output-----
 - In the first line, print the maximum possible value of the final element in the sequence.
 - In the second line, print the number of operations that you perform.
 - In the (2+i)-th line, if the element chosen in the i-th operation is the x-th element from the left in the sequence at that moment, print x.
 - If there are multiple ways to achieve the maximum value of the final element, any of them may be printed.

-----Sample Input-----
5
1 4 3 7 5

-----Sample Output-----
11
3
1
4
2

The sequence would change as follows:
 - After the first operation: 4, 3, 7, 5
 - After the second operation: 4, 3, 7
 - After the third operation: 11(4+7)

Difficulty: competition

Starter code:

Solutions:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n, = map(int,input().split())
*a, = map(int,input().split())

if all(i <= 0 for i in a):
    m = max(a)
    idx = a.index(m)
    print(m)
    print(n-1)
    for i in range(idx):
        print(1)
    for i in range(n-idx-1):
        print(n-idx-i)
    return

even = a[::2]
odd = a[1::2]

se = sum(i for i in even if i > 0)
so = sum(i for i in odd  if i > 0)

res = []
if se < so:
    res.append(1)
    a.pop(0)
    n -= 1
# 0,2,4,6,....-th から
if len(a)%2==0:
    res.append(n)
    a.pop()
    n -= 1
while len(a) > 1:
    n = len(a)
    if a[-1] <= 0:
        res.append(n)
        a.pop()
        res.append(n-1)
        a.pop()
    else:
        if a[-3] > 0:
            res.append(n-1)
            a[-3] += a[-1]
            a.pop()
            a.pop()
        else:
            if len(a) == 3:
                res += [1,1]
                a.pop(0)
                a.pop(0)
            else:
                res.append(n-2)
                a.pop(n-3)
                a.pop(n-3)


assert a[0] == max(se,so)
print(max(se,so))
print(len(res))
print(*res,sep="\n")


import sys
N = int(input())
a = [(int(v),i) for i, v in enumerate(input().split())]
ao = sum([v for v, i in a if i%2 and v>0])
ae = sum([v for v, i in a if not i%2 and v>0])
if max(ao, ae)== 0:
    ai = a.index(max(a))
    Ans = [1]*(ai)+list(range(N-ai,1,-1))
    print(max(a)[0])
    print(len(Ans))
    for i in Ans:
        print(i)
    return
if ao >= ae:
    print(ao)
    yn = [i for v, i in a if i%2 and v>0]
else:
    print(ae)
    yn = [i for v, i in a if not i%2 and v>0]
listyn = [i in yn for i in range(N)]
Ans = []
while not listyn[0]:
    Ans.append(1)
    listyn = listyn[1:]
while not listyn[-1]:
    Ans.append(len(listyn))
    listyn = listyn[:-1]
while True:
    if len(listyn) == 1:
        break
    if len(listyn) == [2,3]:
        Ans.append(2)
        break
    if listyn[2]:
        Ans.append(2)
        listyn = [True] + listyn[3:]
    else:
        Ans.append(3)
        listyn = [True, False] + listyn[4:]
print(len(Ans))
for i in Ans:
    print(i)

N=int(input())
A=list(map(int,input().split()))
data=[[],[]]
flag=[[],[]]
for i in range(N):
    data[i%2].append(A[i])
    flag[0].append(i%2)
    flag[1].append((i+1)%2)

num0=0

for i in range(len(data[0])):
    u=data[0][i]
    if u>0:
        num0+=u
    else:
        flag[0][2*i]=1

if num0==0:
    num0=max(data[0])
    flag[0]=[1 for i in range(N)]
    for i in range(len(data[0])):
        u=data[0][i]
        if u==num0:
            flag[0][2*i]=0
            break
            
num1=0

for i in range(len(data[1])):
    u=data[1][i]
    if u>0:
        num1+=u
    else:
        flag[1][2*i+1]=1
        
if num1==0:
    num1=max(data[1])
    flag[1]=[1 for i in range(N)]
    for i in range(len(data[1])):
        u=data[1][i]
        if u==num1:
            flag[1][2*i+1]=0
            break

if num0>num1:
    print(num0)
    H=flag[0]
else:
    print(num1)
    H=flag[1]
ans=[]
ddd=0
for i in range(N):
    if H[i]==1:
        ans.append(1)
        ddd+=1
    else:
        H=H[i:]
        break   
H=[0]+H
kkk=N-ddd
while True:
    if H[kkk]==1:
        ans.append(kkk)
        kkk-=1
    else:
        break

while kkk>0:
    if H[kkk]==0:
        kkk-=1
    else:
        cnt=0
        while H[kkk]==1:
            kkk-=1
            cnt+=1
        for j in range((cnt+1)//2,0,-1):
            ans.append(kkk+j)

print(len(ans))
for u in ans:
    print(u)

n = int(input())
a = list(map(int, input().split()))
use = [False]*n
mx = max(a)
if mx < 0:
    use[a.index(mx)] = True
else:
    evn = sum(max(i, 0) for i in a[::2])
    odd = sum(max(i, 0) for i in a[1::2])
    mx = max(evn, odd)
    for i in range(int(evn<odd), n, 2):
        if a[i] > 0:
            use[i] = True
print(mx)
beg = 0
while not use[beg]:
    beg += 1
res = [1]*beg
end = n-1
while beg < end:
    if use[end]:
        if use[end-2]:
            a[end-2] += a[end]
            res.append(end-beg)
            end -= 2
            use[end] = True
        else:
            res.append(end-beg-1)
            a[end-2] = a[end]
            end -= 2
            use[end] = True
    else:
        res.append(end-beg+1)
        end -= 1
print(len(res))
for i in res:
    print(i)

n = int(input())
a = list(map(int, input().split()))
mx = max(a)
a[a.index(mx)] = abs(mx)
evn = sum(max(0, i) for i in a[::2])
odd = sum(max(0, i) for i in a[1::2])
if mx < 0:
    print(mx)
else:
    print((max(evn, odd)))
oe = int(evn < odd)
res = []
beg = 0
while beg%2!=oe or a[beg]<0:
    res.append(1)
    beg += 1
end = n-1
while end%2!=oe or a[end]<0:
    res.append(end-beg+1)
    end -= 1
while beg < end:
    if a[end-2] < 0:
        res.append(end-beg-1)
    else:
        res.append(end-beg)
    end -= 2
print((len(res)))
for i in res:
    print(i)


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))

    even = sum([max(A[i], 0) for i in range(0, N, 2)])
    odd = sum([max(A[i], 0) for i in range(1, N, 2)])

    if even == odd == 0:
        a = max(A)
        print(a)
        print((N-1))
        flg = 1
        for i in range(N-1):
            if A[i] == a:
                flg = 0
            if flg:
                print((1))
            else:
                print((N-i))
        return

    ans = []
    i = 0
    if odd > even:
        if N % 2 == 1:
            ans.append(N)
            N -= 1
        ans.append(1)
        i = 1
    else:
        if N % 2 == 0:
            ans.append(N)
            N -= 1
    flg = 1
    while True:
        if flg:
            if A[i] > 0:
                flg = 0
            else:
                ans.append(1)
                i += 1
                if i == N:
                    break
                ans.append(1)
                i += 1
                if i == N:
                    break
        else:
            if A[i+2] > 0:
                ans.append(2)
                i += 2
            else:
                ans.append(3)
                i += 2
            if i+2 >= N:
                break
    if ans[-1] == 3:
        ans.append(2)
    print((max(odd, even)))
    print((len(ans)))
    for x in ans:
        print(x)


def __starting_point():
    main()

__starting_point()

N = int(input()) 
A = list(map(int,input().split()))

DP = [(a, -1) for a in A]

for i in range(N):
  for j in range(i+2, N, 2):
    val_nxt = DP[i][0] + A[j]
    if DP[j][0] < val_nxt:
      DP[j] = (val_nxt, i)
    
tmp = -10**20
i_max = -1
for j, dp in enumerate(DP):
  if dp[0] > tmp:
    tmp = dp[0]
    i_max = j
print(tmp)
#print(DP)
#print(i_max)
path = []
i = i_max
while i >= 0:
  path.append(i)
  _, i = DP[i]
  
path.reverse()

sft = 0
ans = []
for _ in range(path[0]):
  ans.append(0)
sft += path[0]
for j in range(1,len(path)):
  i_prv = path[j-1]
  d = path[j] - path[j-1]
  for _ in range((d-1)//2):
    ans.append(i_prv+2-sft)
  ans.append(i_prv+1-sft)
  sft += d
for j in range(N-1,path[-1],-1):
  ans.append(j-sft)
#print(path)    

ans = [a+1 for a in ans]
print(len(ans))
print(*ans, sep="\n")
  
  

import sys
input = sys.stdin.readline
import numpy as np

# 奇数番目、または偶数番目、の好きな部分集合を足せる（ただし1元以上）
# 交互に塗り分けると交互が維持されることから分かる

N = int(input())
A = np.array(input().split(), dtype=np.int64)

def select_operation(select,N):
    result = []
    # 余分な左端
    x = select.min()
    result = [0] * x
    select -= x
    N -= x
    # 余分な右端
    y = select.max()
    result += list(range(N-1,y,-1))
    N = y + 1
    # 右から見て、要らない偶数を除外
    result += np.setdiff1d(np.arange(N)[::2], select)[::-1].tolist()
    # 0,2,4,...番目を集約
    result += [1] * (len(select) - 1)
    result = [1+x for x in result]
    return result

ev_sum = np.maximum(0,A[::2]).sum()
od_sum = np.maximum(0,A[1::2]).sum()
if ev_sum >= od_sum > 0:
    select = np.where(A[::2] >= 0)[0] * 2
elif od_sum > 0:
    select = np.where(A[1::2] >= 0)[0] * 2 + 1
else:
    n = np.argmax(A)
    select = np.array([n])
S = A[select].sum()

ope = select_operation(select,N)

# 答えの出力
print(S)
print(len(ope))
print('\n'.join(map(str,ope)))

select


def main1(n,a):
  # n個の数字。パターン1の操作で1個減る。パターン2の操作で2個減る
  # n<=2000
  # パターン1だけするとき。max(a)が最大
  # パターン2を1回するとき。max(a)かmax(a[i]+a[i+2])が最大
  # パターン2を2回するとき。max(a)かmax(a[i]+a[i+2])かmax(a[i]+a[i+4])かmax(a[i]+a[i+2]+a[i+4])が最大
  # パターン2を3回するとき。max(a[i]+a[i+6])かmax(a[i]+a[i+4]+a[i+6])max(a[i]+a[i+2]+a[i+6])かmax(a[i]+a[i+2]+a[i+4]+a[i+6])が最大
  # 偶奇が異なるidxの要素が足されることがあるか？　ない
  # idx奇数の部分和で最大、つまり、負以外すべて足す。これを偶数でもする
  odary=[]
  odnum=0
  evary=[]
  evnum=0
  for i,x in enumerate(a):
    if x<=0:continue
    if i%2==0:
      evary.append(i)
      evnum+=x
    else:
      odary.append(i)
      odnum+=x
  if odnum==0 and evnum==0:
    mv,mi=a[0],0
    for i,x in enumerate(a):
      if mv<x:
        mv=x
        mi=i
    ret=mv
    ary=[mi]
  elif odnum>evnum:
    ret=odnum
    ary=odary
  else:
    ret=evnum
    ary=evary 
  retary=[]
  m=n
  #print(ary)
  for i in reversed(range(len(ary)-1)):
    t=ary[i+1]-ary[i]
    t//=2
    for j in range(t):
      retary.append((ary[i+1]+ary[i])//2-j+1)
      m-=2
  for _ in range(ary[0]):
    retary.append(1)
    m-=1
  for _ in range(n-1-ary[-1]):
    retary.append(m)
    m-=1
  return ret,retary

def __starting_point():
  n=int(input())
  a=list(map(int,input().split()))
  ret1=main1(n,a)
  print(ret1[0])
  print(len(ret1[1]))
  print(*ret1[1],sep='\n')

__starting_point()

from collections import deque
N=int(input())
As=[int(i) for i in input().split()]
neg_odd,neg_even=deque([]),deque([])
S_odd,S_even=0,0
for i,A in enumerate(As):
  if i%2==0:
    if A>=0:
      S_even+=A
    else:
      neg_even.append(i)
  if i%2==1:
    if A>=0:
      S_odd+=A
    else:
      neg_odd.append(i)
ans=[]
A_size=N
if S_odd==S_even==0:
  a=max(As)
  print(a)
  i=0
  while As[i]!=a:
    ans.append(1)
    i+=1
    A_size-=1
  while A_size>1:
    ans.append(A_size)
    A_size-=1
elif S_odd<=S_even:
  print(S_even)
  if N%2==0:
    ans.append(N)
    A_size-=1
  if neg_even:
    t=0
    while A_size-1==neg_even[-1]:
      neg_even.pop()
      ans.append(A_size)
      ans.append(A_size-1)
      A_size-=2
      if not neg_even:
        break
    if neg_even:
      while t==neg_even[0]:
        neg_even.popleft()
        ans.append(1)
        ans.append(1)
        t+=2
        A_size-=2
        if not neg_even:
          break
    for a in neg_even:
      ans.append(a+1-t)
      A_size-=2
      t+=2
  while A_size>1:
    ans.append(2)
    A_size-=2
else:
  print(S_odd)
  if N%2==1:
    ans.append(N)
    A_size-=1
  ans.append(1)
  A_size-=1
  if neg_odd:
    t=1
    while A_size==neg_odd[-1]:
      neg_odd.pop()
      ans.append(A_size)
      ans.append(A_size-1)
      A_size-=2
      if not neg_odd:
        break
    if neg_odd:
      while t==neg_odd[0]:
        neg_odd.popleft()
        ans.append(1)
        ans.append(1)
        t+=2
        A_size-=2
        if not neg_odd:
          break
    for a in neg_odd:
      ans.append(a-t+1)
      A_size-=2
      t+=2
  while A_size>1:
    ans.append(2)
    A_size-=2
print(len(ans))
for a in ans:
  print(a)

n = int(input())
a = list(map(int, input().split()))
mx = max(a)
a[a.index(mx)] = abs(mx)
evn = sum(max(0, i) for i in a[::2])
odd = sum(max(0, i) for i in a[1::2])
if mx < 0:
    print(mx)
else:
    print(max(evn, odd))
oe = int(evn < odd)
res = []
beg = 0
while beg%2!=oe or a[beg]<0:
    res.append(1)
    beg += 1
end = n-1
while end%2!=oe or a[end]<0:
    res.append(end-beg+1)
    end -= 1
while beg < end:
    if a[end-2] < 0:
        res.append(end-beg-1)
    else:
        res.append(end-beg)
    end -= 2
print(len(res))
for i in res:
    print(i)

def main():
    from itertools import accumulate
    n = int(input())
    a = list(map(int, input().split()))
    h = (n+1) // 2
    m1 = sum([max(i, 0) for i in a[::2]])
    m2 = sum([max(i, 0) for i in a[1::2]])
    m = max(m1, m2)
    if max(a) < 0:
        m = max(a)
    flag = False
    ans = []
    if m == m1 or m == m2:
        if m2 == m:
            n -= 1
            h = (n+1)//2
            a.pop(0)
            ans.append(1)
        for i in range(h):
            if a[2*i] < 0:
                if flag == False:
                    ans.append(1)
                    ans.append(1)
                else:
                    ans.append(3)
            else:
                if flag:
                    ans.append(2)
                else:
                    flag = True
        if ans[-1] == 3 or n%2 == 0:
            ans.append(2)
    else:
        for i in range(n):
            if a[i] != m:
                ans.append(1)
            else:
                for j in range(n-i, 1, -1):
                    ans.append(j)
                break
    print(m)
    print((len(ans)))
    for i in ans:
        print(i)

    

main()



"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc092/tasks/arc092_c

寄与を残せる要素ってどんな集合？

→少なくとも連続する2つは絶対残せない
→残せるのは、偶数番目 or 奇数番目　のみ？

→少なくとも、偶奇が違う二つの要素を同時に残す方法は見当たらない

構築→右端から構築していくのが楽？(indexが変化しないので)
後ろから見ていって、取らないと決めたindと、取ると決めたやつ+1を選んでいけばよい

全て負の時はコーナーケース
"""

import sys
N = int(input())

a = list(map(int,input().split()))

esum = 0
osum = 0

if max(a) < 0:
    #コーナーケース

    maxind = 0
    for i in range(N):
        if a[maxind] < a[i]:
            maxind = i

    rem = N
    print((a[maxind]))
    print((N-1))
    for i in range(maxind):
        print((1))
        rem -= 1
    while rem != 1:
        print (rem)
        rem -= 1
    return

eve = 0
eflag = [False] * N
epicks = []
odd = 0
oflag = [False] * N
opicks = []
for i in range(N):

    if i % 2==0 and a[i] >= 0:
        eflag[i] = True
        eve += a[i]
        epicks.append(i)
    if i % 2==1 and a[i] >= 0:
        oflag[i] = True
        odd += a[i]
        opicks.append(i)

if eve > odd:

    print (eve)
    ans = []

    for i in range(N-1,-1,-1):

        if i < epicks[0]:
            ans.append(1)
        elif i % 2 == 0 and eflag[i] == False:
            ans.append(i+1)
        elif i % 2 == 1 and eflag[i-1] == True:
            ans.append(i+1)

    print((len(ans)))
    print(("\n".join(map(str,ans))))

else:

    print (odd)
    ans = []

    for i in range(N-1,-1,-1):

        if i < opicks[0]:
            ans.append(1)
        elif i % 2 == 1 and oflag[i] == False:
            ans.append(i+1)
        elif i % 2 == 0 and oflag[i-1] == True:
            ans.append(i+1)

    print((len(ans)))
    print(("\n".join(map(str,ans))))