— Oh my sweet Beaverette, would you fancy a walk along a wonderful woodland belt with me?  

 — Of course, my Smart Beaver! Let us enjoy the splendid view together. How about Friday night? 

At this point the Smart Beaver got rushing. Everything should be perfect by Friday, so he needed to prepare the belt to the upcoming walk. He needed to cut down several trees.

Let's consider the woodland belt as a sequence of trees. Each tree i is described by the esthetic appeal a_{i} — some trees are very esthetically pleasing, others are 'so-so', and some trees are positively ugly!

The Smart Beaver calculated that he needed the following effects to win the Beaverette's heart:   The first objective is to please the Beaverette: the sum of esthetic appeal of the remaining trees must be maximum possible;  the second objective is to surprise the Beaverette: the esthetic appeal of the first and the last trees in the resulting belt must be the same;  and of course, the walk should be successful: there must be at least two trees in the woodland belt left. 

Now help the Smart Beaver! Which trees does he need to cut down to win the Beaverette's heart?


-----Input-----

The first line contains a single integer n — the initial number of trees in the woodland belt, 2 ≤ n. The second line contains space-separated integers a_{i} — the esthetic appeals of each tree. All esthetic appeals do not exceed 10^9 in their absolute value.  to get 30 points, you need to solve the problem with constraints: n ≤ 100 (subproblem A1);  to get 100 points, you need to solve the problem with constraints: n ≤ 3·10^5 (subproblems A1+A2). 


-----Output-----

In the first line print two integers — the total esthetic appeal of the woodland belt after the Smart Beaver's intervention and the number of the cut down trees k.

In the next line print k integers — the numbers of the trees the Beaver needs to cut down. Assume that the trees are numbered from 1 to n from left to right.

If there are multiple solutions, print any of them. It is guaranteed that at least two trees have equal esthetic appeal.


-----Examples-----
Input
5
1 2 3 1 2

Output
8 1
1 
Input
5
1 -2 3 1 -2

Output
5 2
2 5

Source: codeforces | Difficulty: MEDIUM
Tags: Implementation

Complete search


Solutions:
import sys
fin = sys.stdin
n = int(fin.readline())
a = list(map(int, fin.readline().split()))
table = dict()
s = [0] * (n + 1)
for i in range(n):
	rec = table.setdefault(a[i], {'begin': i, 'end': i, 'sum': a[i]})
	rec['end'] = i
	if a[i] >= 0:
		s[i + 1] = s[i] + a[i]
		rec['sum'] = s[rec['end'] + 1] - s[rec['begin']]
	else:
		s[i + 1] += s[i]
		rec['sum'] = s[rec['end'] + 1] - s[rec['begin']] + 2 * a[i]
ms = max((v['sum'] for v in table.values() if v['begin'] != v['end']))
for mi in table.keys():
	if table[mi]['sum'] == ms:
		break
mr = [i + 1 for i in range(n) if i < table[mi]['begin'] or i > table[mi]['end'] or (table[mi]['begin'] < i < table[mi]['end'] and a[i] < 0)]
print(ms, len(mr))
print(' '.join(map(str, mr)))


from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
same = defaultdict(list)
only_positive = [max(0, x) for x in a]
partial_sum = [0 for i in range(n + 1)]
for i in range(1, n + 1):
	partial_sum[i] = partial_sum[i - 1] + only_positive[i - 1]
for i in range(n):
	same[a[i]].append(i)
best = -10 ** 18
(bl, br) = (-1, -1)
for key in same:
	if len(same[key]) >= 2:
		(l, r) = (same[key][0], same[key][-1])
		cur = key * 2 + partial_sum[r] - partial_sum[l + 1]
		if cur > best:
			best = cur
			(bl, br) = (l, r)
cut = []
for i in range(n):
	if not (a[i] >= 0 and bl <= i and (i <= br)):
		if i != bl and i != br:
			cut.append(i + 1)
print(best, len(cut))
print(*cut)


from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
ans1 = [-10000000000000000, -1, -1]
if a[0] >= 0:
	prefix = [a[0]]
else:
	prefix = [0]
for i in range(1, n):
	if a[i] >= 0:
		prefix.append(a[i] + prefix[-1])
	else:
		prefix.append(prefix[-1])
pos = defaultdict(list)
ans = [-1000000000000000000, -1, -1]
for i in range(n):
	if len(pos[a[i]]) == 0:
		pos[a[i]].append(i)
	elif len(pos[a[i]]) == 1:
		pos[a[i]].append(i)
		if pos[a[i]][0] != 0:
			tot = prefix[i - 1] - prefix[pos[a[i]][0]] + a[pos[a[i]][0]] + a[pos[a[i]][1]]
		else:
			tot = prefix[i - 1] - prefix[0] + a[pos[a[i]][0]] + a[pos[a[i]][1]]
		if ans[0] <= tot:
			ans[0] = tot
			ans[1] = pos[a[i]][0]
			ans[2] = i
	else:
		pos[a[i]][-1] = i
		if pos[a[i]][0] != 0:
			tot = prefix[i - 1] - prefix[pos[a[i]][0]] + a[pos[a[i]][0]] + a[pos[a[i]][1]]
		else:
			tot = prefix[i - 1] - prefix[0] + a[pos[a[i]][0]] + a[pos[a[i]][1]]
		if ans[0] <= tot:
			ans[0] = tot
			ans[1] = pos[a[i]][0]
			ans[2] = i
tree = []
for i in range(ans[1]):
	tree.append(i + 1)
for i in range(ans[1] + 1, ans[2]):
	if a[i] < 0:
		tree.append(i + 1)
for i in range(ans[2] + 1, n):
	tree.append(i + 1)
print(ans[0], len(tree))
print(*tree)


def main():
	(n, aa) = (int(input()), list(map(int, input().split())))
	(partialsum, s, d, ranges) = ([0] * n, 0, {}, [])
	for (hi, a) in enumerate(aa):
		if a in d:
			base = s + a * 2
			for lo in d[a]:
				ranges.append((base - partialsum[lo], lo, hi))
			d[a].append(hi)
		else:
			d[a] = [hi]
		if a > 0:
			s += a
		partialsum[hi] = s
	(s, lo, hi) = max(ranges)
	res = list(range(1, lo + 1))
	for i in range(lo + 1, hi):
		if aa[i] < 0:
			res.append(i + 1)
	res.extend(range(hi + 2, n + 1))
	print(s, len(res))
	print(' '.join(map(str, res)))
main()


N = int(input())

def sum_pos(L):
	n = len(L)
	ans = L[0] + L[-1]
	for i in range(1, n - 1):
		if L[i] > 0:
			ans += L[i]
	return ans
A = input().split()
Removed = []
Positive = []
cost = 0
for i in range(N):
	A[i] = int(A[i])
k = True
for i in range(N):
	for j in range(N - 1, i, -1):
		if A[i] == A[j]:
			costed = sum(A[0:i]) + sum(A[j + 1:])
			if k:
				cost = costed
				start = i
				end = j
				k = False
			elif sum_pos(A[start:end + 1]) < sum_pos(A[i:j + 1]):
				cost = costed
				start = i
				end = j
				k = False
x = cost
for i in range(start):
	Removed.append(i + 1)
for j in range(N - 1, end, -1):
	Removed.append(j + 1)
for i in range(start + 1, end):
	if A[i] < 0:
		Removed.append(i + 1)
ans = sum(A)
for item in Removed:
	ans -= A[item - 1]
Removed.sort()
print(str(ans) + ' ' + str(len(Removed)))
for item in Removed:
	print(item, end=' ')


n = int(input())
v = list(map(int, input().split()))
valmax = max(v) + 100
valmin = min(v) - 100
sol = -10 ** 18
first = {}
last = {}
s = [0 for i in range(-2, n + 5)]
s[0] = max(v[0], 0)
for i in range(1, len(v)):
	s[i] = s[i - 1]
	if v[i] > 0:
		s[i] += v[i]
for i in range(0, len(v)):
	last[str(v[i])] = i
	if not str(v[i]) in first.keys():
		first[str(v[i])] = i
left = 0
right = 0
for i in range(0, len(v)):
	val = v[i]
	if first[str(val)] == last[str(val)]:
		continue
	total = s[last[str(val)]] - s[first[str(val)] - 1]
	if val < 0:
		total += 2 * val
	if total > sol:
		sol = total
		left = first[str(val)]
		right = last[str(val)]
cutTrees = []
for i in range(0, left):
	cutTrees.append(i)
for i in range(left + 1, right):
	if v[i] < 0:
		cutTrees.append(i)
for i in range(right + 1, n):
	cutTrees.append(i)
if n == 2:
	cutTrees = []
print('%i %i' % (sol, len(cutTrees)))
for x in cutTrees:
	print(x + 1, end=' ')


import math
import sys
from collections import deque, Counter, OrderedDict, defaultdict
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
n = inp()
l = inlt()
g = Counter(l)
fst = defaultdict(lambda : -1)
lst = defaultdict(lambda : -1)
sm = [max(0, l[0])]
for i in range(1, n):
	sm.append(sm[-1] + max(0, l[i]))
for i in range(n):
	if fst[l[i]] == -1:
		fst[l[i]] = i
for i in range(n - 1, -1, -1):
	if lst[l[i]] == -1:
		lst[l[i]] = i
mx = -sys.maxsize
v = -1
for each in g:
	if g[each] >= 2:
		if each < 0:
			val = 2 * each - sm[fst[each]] + sm[lst[each]]
		else:
			val = sm[lst[each]] - sm[fst[each]] + each
		if val > mx:
			mx = val
			v = each
cnt = 0
rem = []
for i in range(n):
	if i < fst[v]:
		rem.append(i + 1)
	elif i > lst[v]:
		rem.append(i + 1)
	elif l[i] < 0 and i != fst[v] and (i != lst[v]):
		rem.append(i + 1)
print(mx, len(rem))
print(*rem)


length = int(input())
array = [int(a) for a in input().split()]
maxSum = -1e+21
resIndexes = []
for i in range(length):
	for j in range(length - 1, -1, -1):
		if j > i and array[i] == array[j]:
			tmp = sum(array[i:j + 1])
			indexes = []
			for index in range(i + 1, j):
				if array[index] < 0:
					tmp -= array[index]
					indexes.append(index + 1)
			if tmp > maxSum:
				maxSum = tmp
				indexes += list(range(1, i + 1))
				indexes += list(range(j + 2, length + 1))
				resIndexes = indexes
print(maxSum, len(resIndexes))
result = [str(a) for a in resIndexes]
print(' '.join(result))


from sys import stdin
from collections import defaultdict
n = int(stdin.readline().rstrip())
a = [int(x) for x in stdin.readline().rstrip().split(' ')]
mmin = {}
mmax = {}
pref = {}
for (i, x) in enumerate(a):
	if x not in mmin:
		mmin[x] = i
	mmax[x] = i
	if i == 0:
		val = max(x, 0)
	else:
		val = pref[i - 1] + max(x, 0)
	pref[i] = val
pref[-1] = 0
ks = set(mmin.keys()).intersection(mmax.keys())
fks = [k for k in ks if mmin[k] != mmax[k]]
maxk = None
maxsum = None
for k in fks:
	if maxk is None:
		maxk = k
		maxsum = pref[mmax[k]] - pref[mmin[k] - 1]
		if k < 0:
			maxsum += 2 * k
		continue
	maxcand = pref[mmax[k]] - pref[mmin[k] - 1]
	if k < 0:
		maxcand += 2 * k
	if maxcand > maxsum:
		maxk = k
		maxsum = maxcand
cut = 0
cuts = []
for (i, val) in enumerate(a):
	if i < mmin[maxk] or i > mmax[maxk]:
		cut += 1
		cuts.append(i + 1)
		continue
	if i in [mmin[maxk], mmax[maxk]]:
		continue
	if val < 0:
		cut += 1
		cuts.append(i + 1)
print(maxsum, cut)
print(' '.join((str(x) for x in cuts)))


(n, t) = (int(input()), list(map(int, input().split())))
(a, b) = ({}, {})
for (i, j) in enumerate(t):
	if not j in a:
		a[j] = i
	else:
		b[j] = i
p = [(a[j], b[j] - 1) for j in b]
s = [j if j > 0 else 0 for j in t]
u = v = 2 * t[p[0][0]] - 1
for i in range(n - 1):
	s[i + 1] += s[i]
for (i, j) in p:
	u = 2 * t[i] + s[j] - s[i]
	if u > v:
		(a, b, v) = (i, j, u)
s = list(range(1, a + 1)) + [i for (i, j) in enumerate(t[a + 1:b + 1], a + 2) if j < 0] + list(range(b + 3, n + 1))
print(v, len(s))
print(' '.join(map(str, s)))


n = int(input())
a = tuple(map(int, input().split()))
c = {}
p = {}
s = x = y = 0
m = -1e+18
for i in range(0, len(a)):
	d = c.get(a[i])
	if d != None and s - d + a[i] * 2 > m:
		m = s - d + a[i] * 2
		(x, y) = (p.get(a[i]), i)
	if a[i] > 0:
		s += a[i]
	if p.get(a[i]) == None:
		p[a[i]] = i
		c[a[i]] = s
a = [str(i + 1) for i in range(0, len(a)) if i != x and i != y and (a[i] < 0 or i < x or i > y)]
print(m, len(a))
print(' '.join(a))