Problem:
 Score : 700 points    Problem Statement 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 1 5
1 4 3 7 5      Sample Output 1 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)        Sample Input 2 4
100 100 -1 100      Sample Output 2 200
2
3
1   After the first operation: 100, 200(100+100)  After the second operation: 200        Sample Input 3 6
-1 -2 -3 1 2 3      Sample Output 3 4
3
2
1
2   After the first operation: -4, 1, 2, 3  After the second operation: 1, 2, 3  After the third operation: 4        Sample Input 4 9
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000      Sample Output 4 5000000000
4
2
2
2
2

Solution (Python):
def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N = I()
    A = LI()
    ans = -inf

    S = [0]*(N+1)
    fr = [-1]*N
    best = -1

    for i,a in enumerate(A):
        S[i] = a
        for j in range(i):
            if ((i-j)%2==0):
                if (S[j]+a>S[i]):
                    fr[i] = j
                    S[i] = S[j] + a
            if (S[i]>ans):
                ans = S[i]
                best = i
    
    V = []
    for i in range(best+1,N)[::-1]:
        V.append(i+1)
    i = best
    while(fr[i]>=0):
        f = fr[i]
        
        while(f<i):
            V.append(1+(i+f)//2)
            i -= 2
    for _ in range(i):
        V.append(1)

    print(ans)
    print(len(V))
    for v in V:
        print(v)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

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

even=[0 for i in range(N)]
odd=[0 for i in range(N)]
even[0]=max(0,A[0])
for i in range(1,N):
    if i%2==1:
        even[i]=even[i-1]
        odd[i]=odd[i-1]+max(0,A[i])
    else:
        even[i]=even[i-1]+max(0,A[i])
        odd[i]=odd[i-1]

eval=-10**20
L=-1
R=-1
for i in range(N):
    for j in range(i,N):
        if j==i:
            test=A[i]
            if eval<test:
                eval=test
                L,R=i,i
        elif (j-i)%2==0:
            if i%2==0:
                test=even[j]-even[i-1]*(i!=0)+A[j]*(A[j]<0)+A[i]*(A[i]<0)
                if eval<test:
                    eval=test
                    L,R=i,j
            else:
                test=odd[j]-odd[i-1]*(i!=0)+A[j]*(A[j]<0)+A[i]*(A[i]<0)
                if eval<test:
                    eval=test
                    L,R=i,j

print(eval)
print(N-1-R+L+(R-L)//2)


for i in range(N-1,R,-1):
    print(i+1)

for i in range(L):
    print(1)

for i in range(L+2,R-1,2):
    if A[i]>0:
        print(2)
    else:
        print(3)
        
if L!=R:
    print(2)

Solution (Python):

"""
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
    sys.exit()

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

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()]

if max(A) <= 0:
    ma = - 10 ** 9
    for i, a in enumerate(A):
        if a > ma:
            ma = a
            mai = i
    print(ma)
    print(N - 1)
    for i in range(mai+1, N)[::-1]:
        print(i+1)
    for i in range(mai):
        print(1)
else:
    E = sum([a for a in A[::2] if a > 0])
    O = sum([a for a in A[1::2] if a > 0])
    ANS = []
    if O > E:
        ANS.append(1)
        A = A[1:]
    if len(A) % 2 == 0:
        ANS.append(len(A))
        A.pop()
    
    while len(A) > 1:
        if A[0] < 0:
            ANS.append(1)
            ANS.append(1)
            A = A[2:]
        elif A[-1] < 0:
            ANS.append(len(A))
            A.pop()
            ANS.append(len(A))
            A.pop()
        elif A[-3] < 0:
            ANS.append(len(A) - 2)
            A[-2] = A.pop()
            A.pop()
        else:
            ANS.append(len(A) - 1)
            A[-3] += A[-1]
            A.pop()
            A.pop()
    
    print(A[0])
    print(len(ANS))
    for a in ANS:
        print(a)

Solution (Python):
from itertools import accumulate
n = int(input())
a = list(map(int,input().split()))
x = a[::2]
y = a[1::2]
lx = len(x)
ly = len(y)
sumx = sum([max(x[i],0) for i in range(lx)])
sumy = sum([max(y[i],0) for i in range(ly)])
ansls = []
if sumx >= sumy:
  ans = sumx
  flg = 0
else:
  ans = sumy
  flg = 1
if sumx == sumy == 0:
  ans = max(a)
  t = a.index(max(a))
  print(ans)
  print(n-1)
  for i in range(n,t+1,-1):
    print(i)
  for i in range(t):
    print(1)
  exit()
if flg:
  x = y
  lx = ly
  ansls.append(1)
  n -= 1
ls = [0]
fp = -1
fptmp = 0
for i in range(lx):
  if x[i] >= 0:
    ls.append(1)
    if fp == -1:
      fp = fptmp
  else:
    ls.append(-1)
    fptmp += 1
pnt = (n+1)//2*2-1
if pnt < n:
  ansls.append(n)
flgb = 0
while pnt > 0:
  px = (pnt+1)//2
  if not flgb and ls[px] < 0:
    ansls.append(pnt)
    ansls.append(pnt-1)
    ls.pop()
    pnt -= 2
  elif px <= fp:
    ansls.append(1)
    ansls.append(1)
    pnt -= 2
  elif ls[px] > 0:
    flgb = 1
    if px-1 <= fp:
      pnt -= 2
    elif ls[px-1] < 0:
      ansls.append(pnt-2)
      ls.pop()
      ls.pop()
      ls.append(1)
      pnt -= 2
    else:
      ansls.append(pnt-1)
      ls.pop()
      pnt -= 2
print(ans)
print(len(ansls))
print(*ansls,sep="\n")

Solution (Python):
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)

Solution (Python):
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)
        exit()

    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)


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    sol_tot, sol_tracker = -1e10, []
    for p in range(2):
        c = a.copy()

        idx = np.arange(p, n, 2)
        if len(idx) == 0:
            continue

        pick = max(idx, key=lambda x: c[x])
        if c[pick] <= 0:
            chosen = {pick}
        else:
            chosen = {x for x in idx if c[x] > 0}

        is_chosen, tot, tracker = [False] * n, 0, []
        for i in chosen:
            is_chosen[i] = True
            tot += c[i]

        for i in reversed(range(n)):
            if not is_chosen[i]:
                if i == 0 or i + 1 == len(c):
                    tracker += [i]
                    del c[i], is_chosen[i]
                elif is_chosen[i - 1] == is_chosen[i + 1]:
                    tracker += [i]
                    c[i - 1] += c[i + 1]
                    del c[i + 1], c[i], is_chosen[i + 1], is_chosen[i]

        if len(c) > 1 and not is_chosen[0]:
            tracker += [0]
            del c[0], is_chosen[0]

        if tot > sol_tot:
            sol_tot, sol_tracker = tot, np.array(tracker) + 1

    print(sol_tot, len(sol_tracker), *sol_tracker, sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    sol_tot, sol_tracker = -1e10, []
    for p in range(2):
        c = a.copy()

        idx = np.arange(p, n, 2)
        if len(idx) == 0:
            continue

        pick = max(idx, key=lambda i: c[i])
        if c[pick] <= 0:
            chosen = set([pick])
        else:
            chosen = set(filter(lambda i: c[i] > 0, idx))

        is_chosen, tot, tracker = [False] * n, 0, []
        for i in chosen:
            is_chosen[i] = True
            tot += c[i]

        for i in reversed(range(n)):
            if not is_chosen[i]:
                if i == 0 or i + 1 == len(c):
                    tracker += [i]
                    del c[i], is_chosen[i]
                elif is_chosen[i - 1] == is_chosen[i + 1]:
                    tracker += [i]
                    c[i - 1] += c[i + 1]
                    del c[i + 1], c[i], is_chosen[i + 1], is_chosen[i]

        if len(c) > 1 and not is_chosen[0]:
            tracker += [0]
            del c[0], is_chosen[0]

        if tot > sol_tot:
            sol_tot, sol_tracker = tot, np.array(tracker) + 1

    print(sol_tot, len(sol_tracker), *sol_tracker, sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    sol_tot, sol_tracker = int(-1e10), []
    for p in range(2):
        c = a.copy()

        idx = list(range(p, n, 2))
        if not idx:
            continue

        pick = max(idx, key=lambda i: c[i])
        if c[pick] <= 0:
            chosen = set([pick])
        else:
            chosen = set(filter(lambda i: c[i] > 0, idx))

        is_chosen, tot, tracker = [False] * n, 0, []
        for i in chosen:
            is_chosen[i] = True
            tot += c[i]

        for i in reversed(range(n)):
            if not is_chosen[i]:
                if i == 0 or i + 1 == len(c):
                    tracker += [i]
                    del c[i], is_chosen[i]
                elif is_chosen[i - 1] == is_chosen[i + 1]:
                    tracker += [i]
                    c[i - 1] += c[i + 1]
                    del c[i + 1], c[i], is_chosen[i + 1], is_chosen[i]

        if len(c) > 1 and not is_chosen[0]:
            tracker += [0]
            del c[0], is_chosen[0]

        if tot > sol_tot:
            sol_tot, sol_tracker = tot, np.array(tracker) + 1

    print(sol_tot, len(sol_tracker), *sol_tracker, sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    best, solution = int(-1e10), []
    for p in range(2):
        c = a.copy()

        indexes = list(range(p, n, 2))
        if len(indexes) == 0:
            continue

        maks = max([c[i] for i in indexes])
        pick = next(filter(lambda i: c[i] == maks, indexes))
        chosen = set([pick] if maks <= 0 else filter(lambda i: c[i] > 0, indexes))
        is_chosen = [(i in chosen) for i in range(n)]

        tot, res = sum([c[i] for i in chosen]), []
        for i in reversed(range(n)):
            if not is_chosen[i]:
                if i == 0 or i + 1 == len(c):
                    res += [i]
                    del c[i], is_chosen[i]
                elif is_chosen[i - 1] == is_chosen[i + 1]:
                    res += [i]
                    c[i - 1] += c[i + 1]
                    del c[i + 1], c[i], is_chosen[i + 1], is_chosen[i]

        if len(c) > 1 and not is_chosen[0]:
            res += [0]
            del c[0], is_chosen[0]

        if tot > best:
            best, solution = tot, np.array(res) + 1

    print(best, len(solution), *solution, sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    best, solution = int(-1e10), []
    for p in range(2):
        c = a.copy()

        indexes = list(range(p, n, 2))
        if len(indexes) == 0:
            continue

        maks = max([c[i] for i in indexes])
        pick = next((i for i in indexes if c[i] == maks))
        chosen = set([pick] if maks <= 0 else [i for i in indexes if c[i] > 0])
        is_chosen = [(i in chosen) for i in range(n)]

        tot, res = sum([c[i] for i in chosen]), []
        for i in reversed(range(n)):
            if not is_chosen[i]:
                if i == 0 or i + 1 == len(c):
                    res += [i]
                    del c[i], is_chosen[i]
                elif is_chosen[i - 1] == is_chosen[i + 1]:
                    res += [i]
                    c[i - 1] += c[i + 1]
                    del c[i + 1], c[i], is_chosen[i + 1], is_chosen[i]

        if len(c) > 1 and not is_chosen[0]:
            res += [0]
            del c[0], is_chosen[0]

        if tot > best:
            best, solution = tot, np.array(res) + 1

    print(best, len(solution), *solution, sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    best, solution = int(-1e10), []
    for p in range(2):
        c = a.copy()

        indexes = list(range(p, n, 2))
        if len(indexes) == 0:
            continue

        maks = max([c[i] for i in indexes])
        pick = next((i for i in indexes if c[i] == maks))
        chosen = set([pick] if maks <= 0 else [i for i in indexes if c[i] > 0])
        is_chosen = [(i in chosen) for i in range(n)]

        tot, res = sum([c[i] for i in chosen]), []
        for i in reversed(range(n)):
            if not is_chosen[i]:
                if i == 0 or i + 1 == len(c):
                    res += [i]
                    del c[i], is_chosen[i]
                elif is_chosen[i - 1] == is_chosen[i + 1]:
                    res += [i]
                    c[i - 1] += c[i + 1]
                    del c[i + 1], c[i], is_chosen[i + 1], is_chosen[i]

        for end in (0, ):
            while len(c) > 1 and not is_chosen[end]:
                res += [end]
                del c[end], is_chosen[end]

        if tot > best:
            best, solution = tot, np.array(res) + 1

    print(best, len(solution), *solution, sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    best, solution = int(-1e10), []
    for p in range(2):
        c = a.copy()

        indexes = list(range(p, n, 2))
        if len(indexes) == 0:
            continue

        maks = max([c[i] for i in indexes])
        pick = next((i for i in indexes if c[i] == maks))
        chosen = set([pick] if maks <= 0 else [i for i in indexes if c[i] > 0])
        is_chosen = [(i in chosen) for i in range(n)]

        tot, res = sum([c[i] for i in chosen]), []
        for i in reversed(range(n)):
            if not is_chosen[i]:
                if i == 0 or i + 1 == len(c):
                    res += [i]
                    del c[i], is_chosen[i]
                elif is_chosen[i - 1] == is_chosen[i + 1]:
                    res += [i]
                    c[i - 1] += c[i + 1]
                    del c[i + 1], c[i], is_chosen[i + 1], is_chosen[i]

        for end in (-1, 0):
            while len(c) > 1 and not is_chosen[end]:
                res += [end]
                del c[end], is_chosen[end]

        if tot > best:
            best, solution = tot, np.array(res) + 1

    print(best, len(solution), *solution, sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    s0 = 0
    s = 0
    i0 = []
    ii = []
    for i, a in enumerate(aa):
        if a < 0: continue
        if i % 2:
            s += a
            ii += [i]
        else:
            s0 += a
            i0 += [i]
    
    if not ii + i0:
        s = max(aa)
        print(s)
        print(n - 1)
        for i in range(n - 1, -1, -1):
            if aa[i] == s:
                break
            print(i + 1)
        for _ in range(i):
            print(1)
        exit()
    if s0 > s:
        s = s0
        ii = i0
    
    
    ans = list(range(n - 1, ii[-1], -1))
    
    for j in range(len(ii) - 2, -1, -1):
        l, r = ii[j], ii[j + 1]
        ans += list(range((l + r) // 2, l, -1))
    
    ans += [0] * ii[0]
    
    print(s)
    print(len(ans))
    for a in ans:
        print(a + 1)

main()

Solution (Python):
def p(i):
    answer.append(i+ 1)
    if i == 0 or i == len(a)-1:
        a.pop(i)
        return
    a.pop(i)
    a[i - 1] += a[i]
    a.pop(i)
    

n = int(input())
a = [int(i) for i in input().split()[:]]

odd_max = 0
even_max = 0
for i in range(n):
    if a[i] > 0:
        if i % 2 == 0:
            odd_max += a[i]
        else:
            even_max +=a[i]

answer = []

if odd_max == even_max == 0:
    max = -1000000001
    ind = 0
    for i in range(n):
        if a[i] > max:
            max = a[i]
            ind = i
    print(a[ind])
    print(n-1)
    for i in range(n - 1, ind, -1):
        print(i+1)
    for i in range(ind):
        print(1)
    quit()




neg = []
flag = 0
if odd_max < even_max: flag = 1
for i in range(n-1,-1,-1):
    if a[i] < 0 and i % 2 == flag:
        neg.append(i)


for i in range(len(neg)):
    p(neg[i])
k = len(a)
if 1 in answer: flag = 1-flag
for i in range(k-1,-1,-1):
    if i % 2 != flag:
        p(i)

print(max(odd_max,even_max))
print(len(answer))
for i in range(len(answer)):
    print(answer[i])

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
ans1 = sum([a[i] for i in range(0, n, 2) if a[i] > 0])
ans2 = sum([a[i] for i in range(1, n, 2) if a[i] > 0])
if max(ans1, ans2) == 0:
	print(max(a))
	print(n-1)
	i_max = a.index(max(a))
	print(*list(range(n, i_max+1, -1)), sep="\n")
	if i_max:
		print(*[1 for _ in range(i_max)], sep="\n")

elif ans1 >= ans2:
	print(ans1)
	op = []
	left = 0
	while a[left] <= 0:
		left += 2

	right = True
	in_seg = False
	for i in range(n-1, -1, -1):
		if right:
			if i%2 == 1 or a[i] <= 0:
				op.append(i+1)
			else:
				right = False
		elif i < left:
			op += [1] * (i+1)
			break
		else:
			if in_seg == False and i%2 == 1:
				in_seg = True
				seg_right = i
			elif i%2 == 0 and a[i] > 0:
				in_seg = False
				op += list(range((i+seg_right+3)//2, i+1, -1))

	print(len(op))
	print(*op, sep="\n")

else:
	print(ans2)
	op = []
	left = 1
	while a[left] <= 0:
		left += 2

	right = True
	in_seg = False
	for i in range(n-1, -1, -1):
		if right:
			if i%2 == 0 or a[i] <= 0:
				op.append(i+1)
			else:
				right = False
		elif i < left:
			op += [1] * (i+1)
			break
		else:
			if in_seg == False and i%2 == 0:
				in_seg = True
				seg_right = i
			elif i%2 == 1 and a[i] > 0:
				in_seg = False
				op += list(range((i+seg_right+3)//2, i+1, -1))

	print(len(op))
	print(*op, sep="\n")

Solution (Python):
N = int(input())
A_ = list(map(int, input().split()))
ma = -float("inf")
ama = -1
for i, a in enumerate(A_):
    if a>0:
        break
    if ma < a:
        ma = a
        ama = i
else:
    print(ma)
    print(N-1)
    Ans = []
    for i in range(N, ama+1, -1):
        Ans.append(i)
    for i in range(ama):
        Ans.append(1)
    print("\n".join(map(str, Ans)))
    exit()

A = A_[:]

R1 = []
an1 = 0
for i in range(0, N, 2):
    a = A[i]
    if a>=0:
        an1 += a
    else:
        R1.append(i)
idx_r1 = i
R2 = []
an2 = 0
for i in range(1, N, 2):
    a = A[i]
    if a>=0:
        an2 += a
    else:
        R2.append(i)
idx_r2 = i
ans, R, idx_r = (an1, R1, idx_r1) if an1 > an2 else (an2, R2, idx_r2)
idx_r += 1
print(ans)
Ans = []

for idx in R[::-1]:
    del A[idx]
    if 1<=idx<len(A):
        A[idx-1] += A.pop(idx)
    elif idx==0:
        idx_r -= 1
    Ans.append(idx+1)
for idx in range(idx_r, -1, -2):
    if 0<=idx<len(A):
        del A[idx]
        if 1<=idx<len(A):
            A[idx-1] += A.pop(idx)
        Ans.append(idx+1)

for idx in Ans:
    del A_[idx-1]
    if 1<idx<=len(A):
        A[idx-2] += A.pop(idx-1)

assert len(A)==1 and A[0]==ans

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

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np




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

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
f = 1
for i in range(n):
    if a[i]>0:
        f = 0
if f:
    ind = a.index(max(a))
    print(max(a))
    list = []
    for i in range(n,ind+1,-1):
        list.append(i)
    for _ in range(ind):
        list.append(1)
    print(len(list))
    for i in list:
        print(i)
    exit()
g1 = a[1::2]
g2 = a[::2]
ans1,ans2 = 0,0
l1,l2 = [],[]
for i in range(len(g1)):
    if g1[i]>0:
        ans1 += g1[i]
        l1.append(i*2+2)
for i in range(len(g2)):
    if g2[i]>0:
        ans2 += g2[i]
        l2.append(i*2+1)
length = n
if ans1>=ans2:
    print(ans1)
    list = []
    for i in range(n,l1[-1],-1):
        list.append(i)
    length -= n-l1[-1]
    for i in range(l1[-1],l1[0],-2):
        if not i in l1:
            list.append(i)
            length -= 2
    for i in range(l1[0]-1):
        list.append(1)
    length -= l1[0]
    for _ in range(length,0,-2):
        list.append(2)
    print(len(list))
    for i in list:
        print(i)
else:
    print(ans2)
    list = []
    for i in range(n,l2[-1],-1):
        list.append(i)
    length -= n-l2[-1]
    for i in range(l2[-1],l2[0],-2):
        if not i in l2:
            list.append(i)
            length -= 2
    for i in range(l2[0]-1):
        list.append(1)
    length -= l2[0]
    for _ in range(length,0,-2):
        list.append(2)
    print(len(list))
    for i in list:
        print(i)

Solution (Python):



def solve(n, aa):

    opa = []

    a_max = max(aa)

    if a_max <= 0:
        print(a_max)
        x = aa.index(a_max) + 1
        for i in range(n, x, -1):
            opa.append(i)
        for i in range(1, x):
            opa.append(1)
    else:
        sum0 = 0
        sum1 = 0
        for i in range(n):
            a = aa[i]
            if 0 < a:
                if i % 2 == 0:
                    sum0 += a
                else:
                    sum1 += a
        print(max(sum0, sum1))

        used = [False] * n
        i0 = 1 if sum0 < sum1 else 0
        for i in range(i0, n, 2):
            if 0 < aa[i]:
                used[i] = True

        k = n
        for i in range(n - 1, -1, -1):
            if not used[i]:
                opa.append(i + 1)
                k -= 1
            else:
                break
        j = 0
        for i in range(k):
            if not used[i]:
                opa.append(1)
                j += 1
            else:
                break

        c = 0
        for i in range(k - 1, j - 1, -1):
            if used[i]:
                c = 0
            else:
                c += 1
                if c == 3:
                    opa.append(i - j + 2)
                    k -= 2
                    c = 1

        for i in range((k - j) // 2):
            opa.append(2)


    print(len(opa))
    for v in opa:
        print(v)


def main():
    n = input()
    n = int(n)
    aa = list(map(int, input().split()))

    solve(n, aa)


if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):
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)
    sys.exit()
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)