Buggy python submission (verdict: Runtime Error):
#!/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()

    memo = {}
    def calc(l, r):
        if l > r: return (0, [])
        if (l,r) in memo: return memo[(l,r)]
        if r-l == 0:
            res = (a[r], [])
        elif r-l == 1:
            if a[l] > a[r]:
                res = (a[l], [r])
            else:
                res = (a[r], [l])
        else:
            ma = -float('inf')
            for i in xrange(l, r+1):
                c11, c12 = calc(l, i-1)
                c21, c22 = calc(i+1, r)
                if c11+c21 > ma:
                    res = (c11+c21, c12+c22+[i])
                    ma = c11+c21

        memo[(l,r)] = res
        return res

    ans = []
    num, pro = calc(0, n-1)
    ans.append(num)
    ans.append(len(pro))

    while len(pro) > 0:
        p = pro.pop()
        ans.append(p+1)
        if p == 0 or p == n-1:
            diff = 1
        else:
            diff = 2
        for i in xrange(len(pro)):
            if pro[i] > p: pro[i] -= diff
        n -= diff

    return "\n".join(map(str, ans))


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)


Fixed submission:
#!/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)