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



Sample input:
5
1 4 3 7 5


Sample output:
11
3
1
4
2

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def check(A, operations):
    c = A[:]
    for o in operations:
        if o == 1:
            A = A[1:]
        elif o == len(A):
            A = A[:len(A) - 1]
        else:
            o -= 1
            A = A[:o - 1] + [A[o - 1] + A[o + 1]] + A[o + 2:]

    if len(A) != 1:
        print(c)
        print(operations)
    assert(len(A) == 1)
    return A[0]


def solve(N, A):

    if max(A) < 0:
        ans = max(A)
        idx = A.index(ans)
        operations = []
        for i in range(N, idx + 1, -1):
            operations.append(i)
        for i in range(1, idx + 1):
            operations.append(1)
        return ans, operations

    ans = 0
    middle = []
    start, end = None, None
    for i in range(0, N, 2):
        if A[i] >= 0:
            ans += A[i]
            if start is None:
                start = i
            end = i
        else:
            if start is not None:
                middle.append(i)

    operations = []
    num = 0
    for i in range(end + 1, N):
        operations.append(N - num)
        num += 1

    for i in middle[::-1]:
        if start < i < end:
            operations.append(i + 1)
            num += 2

    for i in range(start):
        operations.append(1)
        num += 1

    for i in range((N - num) // 2):
        operations.append(2)

    return ans, operations


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

    ans1, ope1 = solve(N, A[:])
    ans2, ope2 = solve(N - 1, A[1:])
    ope2 = [1] + ope2

    if ans1 > ans2:
        print(ans1)
        print(len(ope1))
        print(*ope1, sep="\n")
    else:
        print(ans2)
        print(len(ope2))
        print(*ope2, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def check(A, operations):
    c = A[:]
    for o in operations:
        if o == 1:
            A = A[1:]
        elif o == len(A):
            A = A[:len(A) - 1]
        else:
            o -= 1
            A = A[:o - 1] + [A[o - 1] + A[o + 1]] + A[o + 2:]

    if len(A) != 1:
        print(c)
        print(operations)
    assert(len(A) == 1)
    return A[0]


def solve(N, A):
    ans1 = 0
    del1 = []
    ok1 = False
    start1, end1 = None, None
    for i in range(0, N, 2):
        if A[i] >= 0:
            ans1 += A[i]
            ok1 = True
            if start1 is None:
                start1 = i
            end1 = i
        else:
            if ok1:
                del1.append(i)

    ans2 = 0
    del2 = [1]
    ok2 = False
    start2 = None
    end2 = None
    for i in range(1, N, 2):
        if A[i] >= 0:
            ans2 += A[i]
            ok2 = True
            if start2 is None:
                start2 = i
            end2 = i
        else:
            if ok2:
                del2.append(i)

    ans, dele, start, end = None, None, None, None
    if ok1 and ok2:
        if ans1 > ans2:
            ans, dele, start, end = ans1, del1, start1, end1
        else:
            ans, dele, start, end = ans2, del2, start2, end2
    elif ok1:
        ans, dele, start, end = ans1, del1, start1, end1
    elif ok2:
        ans, dele, start, end = ans2, del2, start2, end2

    if not ok1 and not ok2:
        ans = max(A)
        idx = A.index(ans)
        a = []
        for i in range(N, idx + 1, -1):
            a.append(i)
        for i in range(1, idx + 1):
            a.append(1)
        return ans, a

    else:
        a = []
        num = 0
        for i in range(end + 1, N):
            a.append(N - num)
            num += 1

        for i in dele[::-1]:
            if start < i < end:
                a.append(i + 1)
                num += 2

        for i in range(start):
            a.append(1)
            num += 1

        for i in range((N - num) // 2) :
            a.append(2)

        return ans, a


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

    ans, ope = solve(N, A[:])
    print(ans)
    print(len(ope))
    print(*ope, sep="\n")

    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N = input()
a = map(int, raw_input().split())
S1 = S2 = 0
for i in range(N):
    if i % 2:
        if a[i] > 0:
            S1 += a[i]
    else:
        if a[i] > 0:
            S2 += a[i]
if S1 == S2 == 0:
    print max(a)
    maxm = -INF
    for i in range(N):
        if maxm < a[i]:
            maxm = a[i]
            pos = i
    a[pos] = 1
    if pos % 2:
        S1 = 1
    else:
        S2 = 1
else:
    print max(S1, S2)
ls = []
for i in range(len(a)):
    a[i] = (a[i], (i % 2 == (S1 > S2)))
while True:
    #print a
    flag = True
    for i in range(len(a)):
        if a[i][0] < 0 and a[i][1]:
            ls.append(i + 1)
            if i == 0:
                a = a[1:]
            elif i == len(a) - 1:
                a = a[:-1]
            else:
                S = (a[i - 1][0] + a[i + 1][0], False)
                a = a[:i - 1] + [S] + a[i + 2:]
            flag = False
            break
    if not flag:
        continue
    for i in range(len(a)):
        if not a[i][1]:
            ls.append(i + 1)
            if i == 0:
                a = a[1:]
            elif i == len(a) - 1:
                a = a[:-1]
            else:
                S = (a[i - 1][0] + a[i + 1][0], True)
                a = a[:i - 1] + [S] + a[i + 2:]
            flag = False
            break
    if flag:
        break

print len(ls)
for num in ls:
    print num

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
N = int(input())
*A, = map(int, input().split())

def calc(A):
    if len(A) == 1:
        return [], A[0]
    res = []
    if len(A) % 2 == 0:
        res.append(len(A))
        A = A[:-1]
    if all(a <= 0 for a in A[::2]):
        ma = max(A[::2])
        i = 0
        while A[i] != ma:
            i += 1
            res.append(1)
        j = len(A)
        while i < j-1:
            res.append(j-i)
            j -= 1
        return res, ma

    l = 0; r = len(A)
    while A[0] < 0:
        res.append(1)
        res.append(1)
        A = A[2:]
    v = 0
    while len(A) > 2:
        if A[2] < 0:
            res.append(3)
            if len(A) > 4:
                A = A[:2] + A[4:]
            else:
                A = A[:2]
        else:
            res.append(2)
            A[2] += A[0]
            A = A[2:]
    if len(A) > 1:
        res.append(2)
    return res, A[0]
r, v = calc(A)
if len(A) > 1:
    r0, v0 = calc(A[1:])
    if v < v0:
        r = [1] + r0
        v = v0
print(v, len(r), *r, sep='\n')

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
sys.setrecursionlimit(10000)
# MOD = 10**9 + 7


def solve(f):
    n = f.read_int()
    a = f.read_int_list()

    ma = -float("inf")
    st = None
    for l in xrange(n):
        s = a[l]
        for r in xrange(l+2, n, 2):
            if a[r] > 0: s += a[r]
        if s > ma:
            ma = s
            st = l

    pro = [1] * st
    a = a[st:]
    while len(a) > 1:
        if len(a) == 2:
            pro.append(2)
            a.pop(1)
        elif len(a) == 3:
            if a[2] > 0:
                pro.append(2)
            else:
                pro.append(3)
                pro.append(2)
            a.pop(2)
            a.pop(1)
        else:
            if a[2] > 0:
                pro.append(2)
                a.pop(0)
                a.pop(0)
            else:
                pro.append(3)
                a.pop(1)
                a.pop(2)

    return "\n".join(map(str, [ma, len(pro)]+pro))


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
def solve(n, aaa):
    odd_idx, even_idx = [], []
    odd_sum, even_sum = 0, 0

    for i in range(0, n, 2):
        if aaa[i] > 0:
            even_idx.append(i)
            even_sum += aaa[i]
    for i in range(1, n, 2):
        if aaa[i] > 0:
            odd_idx.append(i)
            odd_sum += aaa[i]

    if odd_sum < even_sum:
        ans = even_sum
        idx = even_idx
    else:
        ans = odd_sum
        idx = odd_idx
    if ans == 0:
        import numpy as np
        i = np.argmax(aaa)
        ans = aaa[i]
        buf = list(range(n, i + 1, -1)) + [1] * i
        return ans, buf

    j = idx[-1]
    buf = list(range(n, j + 1, -1))
    for i in idx[-2::-1]:
        buf.extend(range((i + j) // 2 + 1, i + 1, -1))
        j = i
    buf += [1] * idx[0]
    return ans, buf


n = int(input())
aaa = list(map(int, input().split()))
ans, buf = solve(n, aaa)
print(ans)
print(len(buf))
print('\n'.join(map(str, buf)))

Submission status: Runtime Error

Solution code:
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(N):
        if (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)
#print(L,R)

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

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

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

Submission status: Runtime Error

Solution code:
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(N):
        if (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(L,R)

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

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

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

Submission status: Runtime Error

Solution code:
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(N):
        if (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(L,R)

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

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

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

Submission status: Runtime Error

Solution code:
#!python3

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


class Cell:

    def __init__(self, need, left, right):
        self.need = need
        self.left = left
        self.right = right
    

class CellList:

    def __init__(self, n, s):
        self.n = n
        self.s = s
        w = Cell(0 in s, None, None)
        self.base = w
        for i in range(1, n):
            w = self.add_cell(w, i)
        self.tail = w
        self.history = []
    
    def add_cell(self, w, i):
        elt = Cell(i in self.s, w, w.right)
        w.right = elt
        if elt.right is not None:
            elt.right.left = elt
        return elt

    def select_element(self):
        if self.n == 0:
            return None
        if self.base.need is False:
            self.history.append(1)
            return self.base
        if self.tail.need is False:
            self.history.append(self.n)
            return self.tail
        
        i = 2
        w = self.base.right
        while w.need or w.left.need is not w.right.need:
            w = w.right
            i += 1
        
        self.history.append(i)
        return w

    def delete_cell(self):
        m = self.select_element()
        if m.left is None:
            self.base = m.right
            self.base.left = None
        elif m.right is None:
            self.tail = m.left
            self.tail.right = None
        else:
            m.need = m.right
            m.left = m.left.left
            m.right = m.right.right
            if m.left is None:
                self.base = m
            else:
                m.left.right = m
            if m.right is not None:
                m.right.left = m
            self.n -= 1
        self.n -= 1


def max_set(l):
    if l[-1][0] <= 0:
        w = [l[-1][0], {l[-1][1]}]
    else:
        w = [0, set()]
        for x in l:
            if x[0] > 0:
                w[0] += x[0]
                w[1].add(x[1])
    
    return w


def max_indexes():
    even = [(A[i], i) for i in range(0, N, 2)]
    odd = [(A[i], i) for i in range(1, N, 2)]
    even.sort()
    odd.sort()

    w1 = max_set(even)
    w2 = max_set(odd)

    return max(w1, w2)
        
    
def main():
    v, s = max_indexes()
    
    cl = CellList(N, s)
    while cl.n > 1:
        cl.delete_cell()
    
    print(v)
    print(len(cl.history))
    for x in cl.history:
        print(x)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!python3

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


class Cell:

    def __init__(self, need, left, right):
        self.need = need
        self.left = left
        self.right = right
    

class CellList:

    def __init__(self, n, s):
        self.n = n
        self.s = s
        w = Cell(0 in s, None, None)
        self.base = w
        for i in range(1, n):
            w = self.add_cell(w, i)
        self.tail = w
        self.history = []
    
    def add_cell(self, w, i):
        elt = Cell(i in self.s, w, w.right)
        w.right = elt
        if elt.right is not None:
            elt.right.left = elt
        return elt

    def select_element(self):
        if self.n == 0:
            return None
        if self.base.need is False:
            self.history.append(1)
            return self.base
        if self.tail.need is False:
            self.history.append(self.n)
            return self.tail
        
        i = 2
        w = self.base.right
        while w.need or w.left.need is not w.right.need:
            w = w.right
            i += 1
        
        self.history.append(i)
        return w

    def delete_cell(self):
        m = self.select_element()
        if m.left is None:
            self.base = m.right
            self.base.left = None
        elif m.right is None:
            self.tail = m.left
            self.tail.right = None
        else:
            m.need = True
            m.left = m.left.left
            m.right = m.right.right
            if m.left is None:
                self.base = m
            else:
                m.left.right = m
            if m.right is not None:
                m.right.left = m
            self.n -= 1
        self.n -= 1


def max_set(l):
    if l[-1][0] <= 0:
        w = [l[-1][0], {l[-1][1]}]
    else:
        w = [0, set()]
        for x in l:
            if x[0] > 0:
                w[0] += x[0]
                w[1].add(x[1])
    
    return w


def max_indexes():
    even = [(A[i], i) for i in range(0, N, 2)]
    odd = [(A[i], i) for i in range(1, N, 2)]
    even.sort()
    odd.sort()

    w1 = max_set(even)
    w2 = max_set(odd)

    return max(w1, w2)
        
    
def main():
    v, s = max_indexes()
    
    cl = CellList(N, s)
    while cl.n > 1:
        cl.delete_cell()
    
    print(v)
    print(len(cl.history))
    for x in cl.history:
        print(x)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!python3

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


class Cell:

    def __init__(self, need, left, right):
        self.need = need
        self.left = left
        self.right = right
    

class CellList:

    def __init__(self, n, s):
        self.n = n
        self.s = s
        w = Cell(0 in s, None, None)
        self.base = w
        for i in range(1, n):
            w = self.add_cell(w, i)
        self.tail = w
        self.history = []
    
    def add_cell(self, w, i):
        elt = Cell(i in self.s, w, w.right)
        w.right = elt
        if elt.right is not None:
            elt.right.left = elt
        return elt

    def select_element(self):
        if self.n == 0:
            return None
        if self.base.need is False:
            self.history.append(1)
            return self.base
        if self.tail.need is False:
            self.history.append(self.n)
            return self.tail
        
        i = 2
        w = self.base.right
        while w.need or w.left.need is False or w.right.need is False:
            w = w.right
            i += 1

        self.history.append(i)
        return w

    def delete_cell(self):
        m = self.select_element()
        if m.left is None:
            self.base = m.right
            self.base.left = None
        elif m.right is None:
            self.tail = m.left
            self.tail.right = None
        else:
            m.need = True
            m.left = m.left.left
            m.right = m.right.right
            if m.left is None:
                self.base = m
            else:
                m.left.right = m
            if m.right is not None:
                m.right.left = m
            self.n -= 1
        self.n -= 1


def max_set(l):
    if l[-1][0] <= 0:
        w = [l[-1][0], {l[-1][1]}]
    else:
        w = [0, set()]
        for x in l:
            if x[0] > 0:
                w[0] += x[0]
                w[1].add(x[1])
    
    return w


def max_indexes():
    even = [(A[i], i) for i in range(0, N, 2)]
    odd = [(A[i], i) for i in range(1, N, 2)]
    even.sort()
    odd.sort()

    w1 = max_set(even)
    w2 = max_set(odd)

    return max(w1, w2)
        
    
def main():
    v, s = max_indexes()
    
    cl = CellList(N, s)
    while cl.n > 1:
        cl.delete_cell()
        
    print(v)
    print(len(cl.history))
    for x in cl.history:
        print(x)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
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 tot > best:
            while len(c) > 1 and not is_chosen[c[0]]:
                del c[0], is_chosen[0]
            while len(c) > 1 and not is_chosen[c[-1]]:
                del c[-1], is_chosen[-1]
            best, solution = tot, np.array(res) + 1

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
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)
    # print(a)

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:

    ind = a.index(max(a))
    print(a[ind])
    for i in range(n - 1, ind, -1):
        p(i)
    for i in range(ind):
        p(i)
    print(len(answer))
    for i in range(len(answer)):
        print(answer[i])
    quit()



# print(odd_max,even_max)
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)
# print(neg)




for i in range(len(neg)):
    p(neg[i])

k = len(a)
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])

Submission status: Runtime Error

Solution code:
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))


# a = [3,5,-12,-2,-2,8,9,-3,7,5]
# n = len(a)
# print(a)
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]
# print(odd_max,even_max)
out_max = max(odd_max,even_max)
neg = []
flag = 1 #奇1偶0
if odd_max < even_max: flag = 0
# print(flag)
for i in range(n-1,-1,-1):
    if a[i] < 0 and i % 2 != flag:
        neg.append(i)
# print(neg)

# def p(index):
#     a.pop(index)
#     a[index - 1] += a[index]
#     a.pop(index)
answer = []
for i in range(len(neg)):
    index = neg[i]
    # p(index)
    answer.append(index+1)
    # print(a)

if n % 2 == 0:
    k = n - len(neg) * 2 - 1
    # print(k)
    for i in range(k,0,-2):
        # print(i)
        answer.append(i+flag)
        # print(a)
else:
    k = n - len(neg) * 2 - flag
    # print(k)
    for i in range(k,0,-2):
        # print(i)
        answer.append(i)
        # print(a)

if n % 2 == 1 and flag == 0:
    step = n//2+1

else:
    step = n//2
print(step)
print(out_max)
for i in range(step):
    print(answer[i])

Submission status: Runtime Error

Solution code:
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)
    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)))