AtCoder Regular Contest 092 - Both Sides Merger

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

Starter code:

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


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)


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)


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
		elif 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
		elif 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')
main()


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)


def main1(n, a):
	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
	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()


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


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
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()
	elif a[-3] > 0:
		res.append(n - 1)
		a[-3] += a[-1]
		a.pop()
		a.pop()
	elif 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')


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


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)


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
	elif 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 = [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)


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)
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)
ans = [a + 1 for a in ans]
print(len(ans))
print(*ans, sep='\n')


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


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


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


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


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


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


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


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


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


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


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)


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)