AtCoder Regular Contest 100 - Or Plus Max

There is an integer sequence of length 2^N: A_0, A_1, ..., A_{2^N-1}. (Note that the sequence is 0-indexed.)
For every integer K satisfying 1 \leq K \leq 2^N-1, solve the following problem:
 - Let i and j be integers. Find the maximum value of A_i + A_j where 0 \leq i < j \leq 2^N-1 and (i or j) \leq K.
Here, or denotes the bitwise OR.

-----Constraints-----
 - 1 \leq N \leq 18
 - 1 \leq A_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
A_0 A_1 ... A_{2^N-1}

-----Output-----
Print 2^N-1 lines.
In the i-th line, print the answer of the problem above for K=i.

-----Sample Input-----
2
1 2 3 1

-----Sample Output-----
3
4
5

For K=1, the only possible pair of i and j is (i,j)=(0,1), so the answer is A_0+A_1=1+2=3.
For K=2, the possible pairs of i and j are (i,j)=(0,1),(0,2).
When (i,j)=(0,2), A_i+A_j=1+3=4. This is the maximum value, so the answer is 4.
For K=3, the possible pairs of i and j are (i,j)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3) .
When (i,j)=(1,2), A_i+A_j=2+3=5. This is the maximum value, so the answer is 5.

Difficulty: HARD

Starter code:

Solutions:
from sys import stdin
N = int(stdin.readline())
A = list(map(int, stdin.readline().split()))
A.append(float('-inf'))
dp = []
ans = 0
aaa = []
for i in range(2 ** N):
	if i == 0:
		dp.append((0, -1))
		continue
	(na, nb) = (i, -1)
	for j in range(N):
		if 2 ** j & i > 0:
			(ta, tb) = dp[i ^ 2 ** j]
			if A[na] < A[ta]:
				nb = na
				na = ta
			elif A[nb] < A[ta] and ta != na:
				nb = ta
			if A[nb] < A[tb]:
				nb = tb
	ans = max(A[na] + A[nb], ans)
	aaa.append(ans)
	dp.append((na, nb))
print('\n'.join(map(str, aaa)))


import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
Max = [[(0, A[0])]]
ans = 0
for bit in range(1, 1 << N):
	dic = {bit: A[bit]}
	for i in range(N):
		if bit & 1 << i != 0:
			for (ind, val) in Max[bit - (1 << i)]:
				dic[ind] = val
	com = []
	for (ind, val) in dic.items():
		if len(com) < 2:
			com.append((ind, val))
		elif com[0][1] < com[1][1]:
			if com[0][1] < val:
				com[0] = (ind, val)
			elif com[1][1] < val:
				com[1] = (ind, val)
		elif com[1][1] < val:
			com[1] = (ind, val)
		elif com[0][1] < val:
			com[0] = (ind, val)
	Max.append(com)
	tmp = com[0][1] + com[1][1]
	if tmp > ans:
		ans = tmp
	print(ans)


import sys
input = sys.stdin.readline

def I():
	return int(input())

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

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

def main():
	mod = 10 ** 9 + 7
	N = I()
	A = LI()
	N2 = pow(2, N)
	g = [[0, 0] for _ in range(N2)]
	for i in range(N2):
		g[i][0] = A[i]
	for k in range(N):
		for s in range(N2):
			if s >> k & 1:
				L = [0, 0, 0, 0]
				L[0] = g[s][0]
				L[1] = g[s][1]
				L[2] = g[s ^ 1 << k][0]
				L[3] = g[s ^ 1 << k][1]
				L.sort()
				g[s][0] = L[-1]
				g[s][1] = L[-2]
	ans = 0
	for k in range(1, N2):
		ans = max(ans, sum(g[k]))
		print(ans)
main()


n = int(input())
f = [[a, 1] for a in map(int, input().split())]
dot = lambda p, q: sorted(p + q)[-2:]
for d in range(n):
	for U in range(1 << n):
		if not U >> d & 1:
			f[U | 1 << d] = dot(f[U | 1 << d], f[U])
res = 0
for i in range(1, 1 << n):
	res = max(res, sum(f[i]))
	print(res)


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

class Top2:

	def __init__(self, x=-1, y=-1):
		if x < y:
			(x, y) = (y, x)
		self.val = [x, y]

	def __add__(self, other):
		self.val = sorted(self.val + other.val, reverse=True)[:2]
		return self
n = II()
aa = LI()
dp = [Top2(a) for a in aa]
for i in range(n):
	for j in range((1 << n) - 1, -1, -1):
		if j >> i & 1:
			continue
		dp[j | 1 << i] += dp[j]
mx = -1
for j in range(1, 1 << n):
	mx = max(mx, sum(dp[j].val))
	print(mx)


from itertools import accumulate

def zeta(data, merge):
	n = len(data)
	i = 1
	while i < n:
		j = i
		while j < n:
			data[j] = merge(data[j], data[j & ~i])
			j = j + 1 | i
		i <<= 1
	return data

def solve(A):

	def merge(x, y):
		return tuple(sorted(x + y)[-2:])
	data = [(a,) for a in A]
	zeta(data, merge)
	return accumulate((sum(x) for x in data[1:]), max)

def __starting_point():
	n = int(input())
	A = tuple(map(int, input().split()))
	print(*solve(A), sep='\n')
__starting_point()


j = n = 1 << int(input())
a = [[int(s)] for s in input().split()]
while j > 1:
	j >>= 1
	a = [sorted(a[i] + a[i ^ j] * (i & j > 0))[-2:] for i in range(n)]
for (s, f) in a[1:]:
	j = max(j, s + f)
	print(j)


(N, r, d) = (1 << int(input()), 0, [[int(s)] for s in input().split()])
B = 1
while B < N:
	for i in range(N):
		if i & B:
			d[i] = sorted(d[i ^ B] + d[i])[-2:]
	B <<= 1
for (a, b) in d[1:]:
	r = max(r, a + b)
	print(r)


N = int(input())
A = list(map(int, input().split()))
f = [[a] for a in A]
for i in range(N):
	for j in range(1 << N):
		if j & 1 << i:
			f[j] = sorted(f[j] + f[j ^ 1 << i], reverse=True)[:2]
Ans = [sum(f[1])]
for (a, b) in f[2:]:
	Ans.append(max(Ans[-1], a + b))
print('\n'.join(map(str, Ans)))


n = int(input())
aaa = list(map(int, input().split()))
n2 = 1 << n
dp = [[a, 0] for a in aaa]
for j in range(n):
	b = 1 << j
	for i in range(n2):
		if not i & b:
			(dpi, dpk) = (dp[i], dp[i | b])
			if dpk[0] < dpi[0]:
				dpk[1] = max(dpk[0], dpi[1])
				dpk[0] = dpi[0]
			elif dpk[1] < dpi[0]:
				dpk[1] = dpi[0]
ans = []
tmp = 0
for a in dp[1:]:
	tmp = max(tmp, a[0] + a[1])
	ans.append(tmp)
print(*ans)


import os
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7

def cummax(it, first=-float('inf')):
	cm = first
	ret = []
	for v in it:
		cm = max(v, cm)
		ret.append(cm)
	return ret
N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
SIZE = 2 ** N
dp = [None] * SIZE
for k in range(1, SIZE):
	dp[k] = list(sorted([(A[0], 0), (A[k], k)]))
for k in range(1, SIZE):
	d = 1
	while d < SIZE:
		if k & d == 0 or k - d == 0:
			d <<= 1
			continue
		prev_k = k - d
		(a1, a2) = dp[k]
		(b1, b2) = dp[prev_k]
		if a1 > b2:
			pass
		elif b1 > a2:
			dp[k] = dp[prev_k]
		elif a2 > b2:
			dp[k] = (b2, a2)
		elif b2 > a2:
			dp[k] = (a2, b2)
		d <<= 1
ans = [0] * SIZE
for k in range(1, SIZE):
	((a1, _), (a2, _)) = dp[k]
	ans[k] = a1 + a2
ans = cummax(ans[1:])
print(*ans, sep='\n')


N = int(input())
A = list(map(int, input().split()))
data = [[(A[0], 0), (-1, -1)] for i in range(2 ** N)]
for i in range(1, 2 ** N):
	for j in range(N):
		if i >> j & 1 == 1:
			(a, b) = data[i - 2 ** j]
			if a[0] > data[i][0][0]:
				data[i][1] = data[i][0]
				data[i][0] = a
			elif a[0] > data[i][1][0] and a[1] != data[i][0][1]:
				data[i][1] = a
			if b[0] > data[i][0][0]:
				data[i][1] = data[i][0]
				data[i][0] = b
			elif b[0] > data[i][1][0] and b[1] != data[i][0][1]:
				data[i][1] = b
	a = (A[i], i)
	if a[0] > data[i][0][0]:
		data[i][1] = data[i][0]
		data[i][0] = a
	elif a[0] > data[i][1][0] and a[1] != data[i][0][1]:
		data[i][1] = a
ans = [data[i][0][0] + data[i][1][0] for i in range(2 ** N)]
for i in range(2, 2 ** N):
	ans[i] = max(ans[i], ans[i - 1])
for i in range(1, 2 ** N):
	print(ans[i])


N = int(input())
A = list(map(int, input().split()))
M = 2 ** N
ans = [0] * M
max_list = [0] * M
for i in range(1, M):
	cand = [i]
	ans_cand = []
	ibin = bin(i)[2:].zfill(N)
	for j in range(N):
		if ibin[j] == '1':
			cand.append(max_list[i - 2 ** (N - j - 1)])
			ans_cand.append(ans[i - 2 ** (N - j - 1)])
	cand_set = sorted(list(set(cand)))
	max1 = 0
	max2 = 0
	for c in cand_set:
		Ac = A[c]
		if Ac >= max1:
			max2 = max1
			max1 = Ac
			max_idx = c
		elif Ac > max2:
			max2 = Ac
	ans_cand.append(max1 + max2)
	ans_cand.append(ans[i - 1])
	max_list[i] = max_idx
	ans[i] = max(ans_cand)
	print(ans[i])


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

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

def examE():
	N = I()
	A = LI()
	n = len(A)
	dp = [[0, 0] for _ in range(n)]
	for (i, a) in enumerate(A):
		dp[i][0] = a
	for j in range(N):
		for (i, a) in enumerate(A):
			if i & 1 << j > 0:
				dp[i] = sorted(dp[i & ~(1 << j)] + dp[i], reverse=True)[:2]
	ans = 0
	for v in dp[1:]:
		ans = max(ans, sum(v))
		print(ans)
	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()


import sys
input = sys.stdin.readline
from itertools import accumulate

def merge(x, y):
	(a, b) = dp[x]
	(c, d) = dp[y]
	if a >= c:
		return (a, max(c, b))
	return (c, max(a, d))
n = int(input())
A = tuple(map(int, input().split()))
dp = [(a, 0) for a in A]
for j in range(n):
	for i in range(1 << n):
		if i & 1 << j:
			dp[i] = merge(i, i & ~(1 << j))
L = tuple(accumulate((sum(d) for d in dp), max))
print(*L[1:], sep='\n')


n = int(input())
a = list(map(int, input().split()))
dp = [[ai, 0, i, -1] for (i, ai) in enumerate(a)]
for i in range(1, 2 ** n):
	for j in range(n):
		if i >> j & 1:
			x = dp[i]
			y = dp[i - (1 << j)]
			if x[0] < y[0]:
				(x, y) = (y, x)
			m1 = x[0]
			i1 = x[2]
			if x[2] == y[2]:
				if x[1] > y[1]:
					m2 = x[1]
					i2 = x[3]
				else:
					m2 = y[1]
					i2 = y[3]
			elif x[1] > y[0]:
				m2 = x[1]
				i2 = x[3]
			else:
				m2 = y[0]
				i2 = y[2]
			dp[i] = [m1, m2, i1, i2]
ans = [0]
for i in range(1, 2 ** n):
	tmp = sum(dp[i][:2])
	ans.append(max(ans[-1], tmp))
print('\n'.join(map(str, ans[1:])))


N = int(input())
A = list(map(int, input().split()))
f = [[a, -1] for a in A]
lim = 1 << N
for i in range(N):
	bit = 1 << i
	j = 0
	while j < lim:
		j |= bit
		(a, b) = f[j]
		(c, d) = f[j ^ bit]
		if a < c:
			f[j][0] = c
			f[j][1] = d if d > a else a
		elif b < c:
			f[j][1] = c
		j += 1
ans = sum(f[1])
Ans = [ans]
for (a, b) in f[2:]:
	s = a + b
	if s > ans:
		ans = s
	Ans.append(ans)
print('\n'.join(map(str, Ans)))


def zata(N, A):
	dp = A[:]
	for n in range(N):
		bit = 1 << n
		for i in range(1 << N):
			if i & bit:
				dp[i] = merge(dp[i ^ bit], dp[i])
	return dp

def merge(x, y):
	return sorted(x + y)[:2]
N = int(input())
(A, res) = ([], 0)
for a in map(int, input().split()):
	A.append([-a])
for (a, b) in zata(N, A)[1:]:
	res = min(res, a + b)
	print(-res)


def upd(ary, nary):
	tt = ary + nary
	tt.sort()
	return [tt[-2], tt[-1]]

def main1(n, a):
	dp = [[a[i], 0] for i in range(1 << n)]
	for j in range(n):
		bit = 1 << j
		for i in range(2 ** n):
			if i & bit == 0:
				dp[i | bit] = upd(dp[i ^ bit], dp[i])
	pre = 0
	for (x, y) in dp[1:]:
		pre = max(pre, x + y)
		print(pre)
n = int(input())
a = list(map(int, input().split()))
main1(n, a)


n = int(input())
a = list(map(int, input().split()))
dp1 = [x for x in a]
dp2 = [0 for _ in range(1 << n)]
for j in range(n + 1):
	for i in range(1 << n):
		if i & 1 << j:
			if dp1[i & ~(1 << j)] >= dp1[i]:
				if dp2[i & ~(1 << j)] >= dp1[i]:
					dp2[i] = dp2[i & ~(1 << j)]
				else:
					dp2[i] = dp1[i]
				dp1[i] = dp1[i & ~(1 << j)]
			elif dp1[i & ~(1 << j)] >= dp2[i]:
				dp2[i] = dp1[i & ~(1 << j)]
ans = 0
for i in range(1, 1 << n):
	ans = max(ans, dp1[i] + dp2[i])
	print(ans)


def func():
	N = int(input())
	A = list(map(int, input().split()))
	P = [[(A[0], 0), (0, 0)] for i in range(2 ** N)]
	for i in range(1, 2 ** N):
		if (A[i], i) > P[i][0]:
			P[i][1] = P[i][0]
			P[i][0] = (A[i], i)
		elif (A[i], i) > P[i][1]:
			P[i][1] = (A[i], i)
		for j in range(N):
			if i & 1 << j == 0:
				index = i + (1 << j)
				for k in range(2):
					if P[i][k] > P[index][0]:
						P[index][1] = P[index][0]
						P[index][0] = P[i][k]
					elif P[i][k] > P[index][1] and P[i][k] != P[index][0]:
						P[index][1] = P[i][k]
	ans = 0
	for i in range(1, 2 ** N):
		ans = max(ans, P[i][0][0] + P[i][1][0])
		print(ans)
func()


N = int(input())
As = [(A << 20) + i for (i, A) in enumerate(map(int, input().split()))]

def chmax(i, elem):
	nonlocal dp
	if dp[0][i] < elem:
		dp[1][i] = dp[0][i]
		dp[0][i] = elem
		return True
	elif dp[1][i] < elem < dp[0][i]:
		dp[1][i] = elem
		return True
	else:
		return False
dp = [[0] * len(As) for _ in range(2)]
dp[0][0] = As[0]
ans = 0
for i in range(1, 2 ** N):
	for j in range(N):
		if i & 1 << j:
			if chmax(i, dp[0][i & ~(1 << j)]):
				chmax(i, dp[1][i & ~(1 << j)])
	chmax(i, As[i])
	ans = max(ans, dp[0][i] + dp[1][i] >> 20)
	print(ans)


from sys import stdin
readline = stdin.readline
n = int(readline())
a = list(map(int, readline().split()))
k_max = 1 << n
dp = [[a[i], 0] for i in range(k_max)]
for i in range(n):
	bit = 1 << i
	for src in range(k_max):
		if bit & src:
			continue
		dst = bit | src
		max_values = dp[dst] + dp[src]
		max_values.sort()
		dp[dst] = [max_values[-1], max_values[-2]]
ans = 0
for k in range(1, k_max):
	ans = max(ans, dp[k][0] + dp[k][1])
	print(ans)


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

def func():
	N = int(input())
	A = list(map(int, input().split()))
	P = [[(A[0], 0), (0, 0)] for i in range(2 ** (N + 1))]
	A = [0] * 2 ** N + A
	for i in range(2 ** N + 1, 2 ** (N + 1)):
		if (A[i], i - 2 ** N) > P[i][0]:
			P[i][1] = P[i][0]
			P[i][0] = (A[i], i - 2 ** N)
		elif (A[i], i) > P[i][1]:
			P[i][1] = (A[i], i - 2 ** N)
		for j in range(N):
			piyo = i - 2 ** N
			if piyo & 1 << j == 0:
				index = piyo + (1 << j) + 2 ** N
				for k in range(2):
					if P[i][k] > P[index][0]:
						P[index][1] = P[index][0]
						P[index][0] = P[i][k]
					elif P[i][k] > P[index][1] and P[i][k] != P[index][0]:
						P[index][1] = P[i][k]
	ans = 0
	for i in range(2 ** N + 1, 2 ** (N + 1)):
		ans = max(ans, P[i][0][0] + P[i][1][0])
		print(ans)
func()


def merge(x, y, z, w):
	P = [x, y, z, w]
	P.sort()
	return (P[-1], P[-2])

def main():
	N = int(input())
	a = list(map(int, input().split()))
	dp = [0] * (2 * (N + 1) * (1 << N))

	def calc(i, j, k):
		return (2 * N + 2) * i + (N + 1) * k + j
	for i in range(1 << N):
		dp[calc(i, 0, 0)] = a[i]
	for j in range(1, N + 1):
		for i in range(1 << N):
			x = calc(i, j, 0)
			y = calc(i & ~(1 << j - 1), j - 1, 0)
			if i & 1 << j - 1:
				(dp[x], dp[x + N + 1]) = merge(dp[y], dp[y + N + 1], dp[x - 1], dp[x + N])
			else:
				(dp[x], dp[x + N + 1]) = (dp[x - 1], dp[x + N])
	result = [0] * (1 << N)
	for k in range(1, 1 << N):
		result[k] = max(result[k - 1], dp[calc(k, N, 0)] + dp[calc(k, N, 1)])
		print(result[k])
	return
main()


def main():
	n = int(input())
	a = list(map(int, input().split()))
	d = [[(j, i), (-1, -1)] for (i, j) in enumerate(a)]
	ans = 0
	for i in range(1, 2 ** n):
		((t1, t2), (t3, t4)) = d[i]
		for j in range(n):
			((t5, t6), (t7, t8)) = d[i & ~(1 << j)]
			if t6 not in [t2, t4]:
				if t5 > t1:
					(t1, t2, t3, t4) = (t5, t6, t1, t2)
				elif t5 > t3:
					(t3, t4) = (t5, t6)
			if t8 not in [t2, t4]:
				if t7 > t3:
					(t3, t4) = (t7, t8)
		d[i] = [(t1, t2), (t3, t4)]
		ans = max(ans, t1 + t3)
		print(ans)
main()


import sys
input = sys.stdin.readline
from heapq import heappushpop
N = int(input())
A = [int(x) for x in input().split()]
B = []
for (n, a) in enumerate(A):
	arr = [(0, 0), (a, n)]
	m = n
	while m:
		bit = m & -m
		((x, i), (y, j)) = B[n - bit]
		if (x, i) != arr[-1]:
			heappushpop(arr, (x, i))
		if (y, j) != arr[-1]:
			heappushpop(arr, (y, j))
		m -= bit
	B.append(arr)
answer = [0]
for ((x, i), (y, j)) in B[1:]:
	z = answer[-1]
	if z < x + y:
		z = x + y
	answer.append(z)
print('\n'.join(map(str, answer[1:])))


from itertools import accumulate
n = int(input())
aaa = list(map(int, input().split()))
n2 = 1 << n
mask = n2 - 1
dp = [[a, 0] for a in aaa]

def update(dpi, dpk):
	if dpk[0] < dpi[0]:
		dpk[1] = max(dpk[0], dpi[1])
		dpk[0] = dpi[0]
	elif dpk[1] < dpi[0]:
		dpk[1] = dpi[0]
for j in range(n):
	b = 1 << j
	c = i = mask ^ b
	while i:
		update(dp[i], dp[i | b])
		i = i - 1 & c
	update(dp[0], dp[b])
ans = list(accumulate(map(sum, dp[1:]), func=max))
print(*ans)


N = int(input())
A = list(map(int, input().split()))
dp = [[A[S], -float('inf')] for S in range(1 << N)]
for i in range(N):
	for T in range(1 << N):
		if T >> i & 1 == 1:
			merge = dp[T] + dp[T ^ 1 << i]
			merge.sort(reverse=True)
			dp[T] = merge[:2]
ans = -float('inf')
for S in range(1, 1 << N, 1):
	ans = max(ans, sum(dp[S]))
	print(ans)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	n = I()
	n2 = 2 ** n
	a = LI()
	t = [[0, 0] for _ in range(n2)]
	ii = [2 ** i for i in range(18)]
	M = n2
	for i in range(n2):
		ti = t[i]
		ti[0] = a[i] * M + i
		for j in range(18):
			if not i & ii[j]:
				continue
			for c in t[i ^ ii[j]]:
				if ti[0] < c:
					ti[1] = ti[0]
					ti[0] = c
				elif ti[1] < c and ti[0] != c:
					ti[1] = c
	r = [0]
	for i in range(1, n2):
		tr = sum(map(lambda x: x // M, t[i]))
		if tr > r[-1]:
			r.append(tr)
		else:
			r.append(r[-1])
	return '\n'.join(map(str, r[1:]))
print(main())


import sys
input = sys.stdin.readline
n = int(input())
alst = list(map(int, input().split()))
max_ = 0
dp = [[a, 0] for a in alst]
for i in range(n):
	for s in range(1 << n):
		if s >> i & 1:
			lst = dp[s] + dp[s - (1 << i)]
			lst.sort(reverse=True)
			dp[s] = lst[:2].copy()
for (a, b) in dp[1:]:
	max_ = max(max_, a + b)
	print(max_)


from copy import deepcopy
N = int(input())
A = [int(i) for i in input().split()]

def chmax(a, b):
	if a[0] < b[1]:
		return b
	elif a[0] < b[0]:
		return (b[0], a[0])
	elif a[1] < b[0]:
		return (a[0], b[0])
	else:
		return a
dp = [(A[i], 0) for i in range(1 << N)]
for i in range(N):
	for j in range(1 << N):
		if j & 1 << i:
			dp[j] = chmax(dp[j], dp[j ^ 1 << i])
ans = sum(dp[0])
for i in range(1, 1 << N):
	t = sum(dp[i])
	ans = max(ans, t)
	print(ans)


import sys
INF = 1 << 60
MOD = 10 ** 9 + 7
sys.setrecursionlimit(2147483647)
input = lambda : sys.stdin.readline().rstrip()

def resolve():
	n = int(input())
	f = [[a, 0] for a in map(int, input().split())]
	dot = lambda p0, p1: sorted(p0 + p1, reverse=1)[:2]
	for i in range(n):
		for U in range(1 << n):
			if not U >> i & 1:
				f[U | 1 << i] = dot(f[U | 1 << i], f[U])
	res = 0
	for i in range(1, 1 << n):
		res = max(res, sum(f[i]))
		print(res)
resolve()


import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
n = int(input())
a = [int(i) for i in readline().split()]

def zeta_transform(a, n):
	b = [[i, 0] for i in a]
	for i in range(n):
		I = 1 << i
		for j in range(1 << n):
			if not j & I:
				if b[j][0] > b[j ^ I][0]:
					(b[j ^ I][0], b[j ^ I][1]) = (b[j][0], b[j ^ I][0])
					if b[j][1] > b[j ^ I][1]:
						b[j ^ I][1] = b[j][1]
				elif b[j][0] > b[j ^ I][1]:
					b[j ^ I][1] = b[j][0]
	return b
za = zeta_transform(a[:], n)
for (i, zi) in enumerate(za):
	if not i:
		ans = 0
	else:
		(i1, i2) = za[i]
		ans = max(ans, i1 + i2)
		print(ans)


def renew(lis, id1, id2):
	tar = lis[id1]
	bow = lis[id2]
	if tar[0] < bow[0]:
		tar = [bow[0], max(bow[1], tar[0])]
	else:
		tar[1] = max(bow[0], tar[1])
	lis[id1] = tar
	return
n = int(input())
a = [[x, 0] for x in list(map(int, input().split()))]
for j in range(n):
	for i in range(2 ** n):
		if not i & 1 << j:
			renew(a, i | 1 << j, i)
a = [x + y for (x, y) in a[1:]]
for i in range(1, 2 ** n - 1):
	if a[i] < a[i - 1]:
		a[i] = a[i - 1]
for x in a:
	print(x)


N = int(input())
A = [[(0, 0)] * (1 << N) for _ in range(N + 1)]
A[0] = [(int(a), 0) for a in input().split()]
combine = lambda a, b: a if a[1] >= b[0] else b if b[1] >= a[0] else (a[0], b[0]) if a[0] > b[0] else (b[0], a[0])
for i in range(1, N + 1):
	ii = 1 << i - 1
	for j in range(1 << N):
		if j & ii:
			A[i][j] = combine(A[i - 1][j], A[i - 1][j ^ ii])
		else:
			A[i][j] = A[i - 1][j]
ANS = [0] * (1 << N)
for i in range(1, 1 << N):
	ANS[i] = max(ANS[i - 1], sum(A[-1][i]))
print('\n'.join(map(str, ANS[1:])))


n = int(input())
a = list(map(int, input().split()))
b = [[i] for i in a]
for j in range(n):
	for i in range(1 << n):
		if i & 1 << j:
			b[i] = sorted(b[i] + b[i ^ 1 << j], reverse=True)[:2]
ans = []
tmp = 0
for i in range(1, 1 << n):
	tmp = max(tmp, sum(b[i]))
	ans.append(tmp)
print(*ans, sep='\n')


n = int(input())
a = [int(i) for i in input().split()]
dp = [[x, 0] for x in range(0, len(a))]

def ins(x, i):
	if x in dp[i]:
		return
	if dp[i][0] != x and a[dp[i][0]] < a[x]:
		dp[i][1] = dp[i][0]
		dp[i][0] = x
	elif dp[i][1] != x and a[dp[i][1]] < a[x]:
		dp[i][1] = x

def mix(i, j):
	ins(dp[i][0], j)
	ins(dp[i][1], j)
for i in range(0, len(a)):
	for j in range(0, n):
		if i & 1 << j == 0:
			mix(i, i | 1 << j)
ans = 0
for i in range(1, len(a)):
	u = a[dp[i][0]] + a[dp[i][1]]
	ans = max(ans, u)
	print(ans)


n = int(input())
aaa = list(map(int, input().split()))
n2 = 1 << n
mask = n2 - 1
dp = [[a, 0] for a in aaa]

def update(dp, i, k):
	(dpi, dpk) = (dp[i], dp[k])
	if dpk[0] < dpi[0]:
		dpk[1] = max(dpk[0], dpi[1])
		dpk[0] = dpi[0]
	elif dpk[1] < dpi[0]:
		dpk[1] = dpi[0]
for j in range(n):
	b = 1 << j
	c = i = mask ^ b
	while i:
		update(dp, i, i | b)
		i = i - 1 & c
	update(dp, 0, b)
ans = []
tmp = 0
for a in dp[1:]:
	tmp = max(tmp, a[0] + a[1])
	ans.append(tmp)
print(*ans)


import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
dp = [[A[i], -1] for i in range(1 << N)]
for i in range(N):
	bit = 1 << i
	for S in range(1 << N):
		if S & bit:
			l = [dp[S][0], dp[S][1], dp[S ^ bit][0], dp[S ^ bit][1]]
			l.sort()
			dp[S][0] = l[-1]
			dp[S][1] = l[-2]
ans = [-1] * (1 << N)
for S in range(1, 1 << N):
	ans[S] = dp[S][0] + dp[S][1]
	if S >= 2:
		ans[S] = max(ans[S], ans[S - 1])
for ans_i in ans[1:]:
	print(ans_i)


def solve():
	N = int(input())
	As = list(map(int, input().split())) + [0]
	pow2 = 2 ** N
	anss = []
	ans = 0
	max2s = [[0, -1]]
	for S in range(1, pow2):
		(m1, m2) = (S, -1)
		for i in range(N):
			if S >> i & 1:
				S0 = S ^ 1 << i
				(i1, i2) = max2s[S0]
				if m1 == i1:
					m2 = m2 if As[m2] >= As[i2] else i2
				elif As[m1] >= As[i1]:
					m2 = m2 if As[m2] >= As[i1] else i1
				else:
					m2 = m1 if As[m1] >= As[i2] else i2
					m1 = i1
		ans2 = As[m1] + As[m2]
		if ans2 > ans:
			ans = ans2
		anss.append(ans)
		max2s.append([m1, m2])
	print('\n'.join(map(str, anss)))
solve()


N = int(input())
A = list(map(int, input().split()))
dp1 = [(0, A[0])]
ans = 0
for i in range(1, 1 << N):
	d = {i: A[i]}
	for k in range(18):
		b = 1 << k
		if i & b == 0:
			continue
		(j, v) = dp1[i - b]
		d.update({j: v})
	(p1, p2) = sorted(list(d.items()), key=lambda x: -x[1])[:2]
	dp1.append(p1)
	ans = max(ans, p1[1] + p2[1])
	print(ans)


import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
zeta = a[:]
zeta2 = [0] * (1 << N)
for i in range(N):
	for j in range(1 << N):
		if 1 << i & j:
			if zeta[j] < zeta[1 << i ^ j]:
				zeta2[j] = max(zeta[j], zeta2[1 << i ^ j])
				zeta[j] = zeta[1 << i ^ j]
			elif zeta2[j] < zeta[1 << i ^ j]:
				zeta2[j] = zeta[1 << i ^ j]
res = 0
for i in range(1, 1 << N):
	res = max(res, zeta[i] + zeta2[i])
	print(res)


import sys
readline = sys.stdin.readline
read = sys.stdin.read
n = int(readline())
(*a,) = list(map(int, readline().split()))
top2 = [[i, 0] for i in a]
for i in range(n):
	i = 1 << i
	for j in range(1 << n):
		if j & i:
			top2[j] = list(sorted(top2[j ^ i] + top2[j]))[2:]
ans = list(map(sum, top2))
for i in range(1, 1 << n):
	ans[i] = max(ans[i], ans[i - 1])
	print(ans[i])


def main():
	n = int(input())
	a = list(map(int, input().split()))
	d = [None] * 2 ** n
	d[0] = [a[0], 0, -1, -1]
	ans = 0
	for (i, t1) in enumerate(a[1:]):
		i += 1
		(t2, t3, t4) = (i, -1, -1)
		for j in range(len(bin(i)) - 2):
			k = i & ~(1 << j)
			if k == i:
				continue
			(t5, t6, t7, t8) = d[k]
			if t5 > t1:
				(t1, t2, t3, t4) = (t5, t6, t1, t2)
			elif t5 > t3:
				if t6 != t2:
					(t3, t4) = (t5, t6)
			if t7 > t3:
				(t3, t4) = (t7, t8)
		d[i] = [t1, t2, t3, t4]
		ans = max(ans, t1 + t3)
		print(ans)
main()


N = int(input())
NN = 1 << N
A = list(map(int, input().split()))
dp1 = A[:]
dp2 = [0] * NN
for k in range(N):
	bit = 1 << k
	for i in range(NN):
		if not i & bit:
			if dp1[i] > dp1[i | bit]:
				dp2[i | bit] = max(dp1[i | bit], dp2[i])
				dp1[i | bit] = dp1[i]
			elif dp1[i] > dp2[i | bit]:
				dp2[i | bit] = dp1[i]
res = 0
for (a, b) in zip(dp1[1:], dp2[1:]):
	res = max(res, a + b)
	print(res)


from heapq import heappush, heappop, heappushpop
N = int(input())
(*A,) = map(int, input().split())

def update(v, que):
	(p, q) = que
	if v == p or v == q:
		return
	heappushpop(que, v)
memo = [None] * 2 ** N
memo[0] = [(0, -1), (A[0], 0)]
ma = 0
ans = []
for i in range(1, 2 ** N):
	res = [(0, -1), (A[i], i)]
	for j in range(N):
		if i >> j & 1 == 0:
			continue
		(p, q) = memo[i ^ 1 << j]
		update(p, res)
		update(q, res)
	(p, q) = memo[i] = res
	ma = max(ma, p[0] + q[0])
	ans.append(ma)
print(*ans, sep='\n')


def max2(p, q):
	(e, b) = (p[0], p[1])
	(c, d) = (q[0], q[1])
	s = list(set([e, b, c, d]))
	(m1, m2) = (1 << n, 1 << n)
	for i in s:
		if a[m1] < a[i]:
			m2 = m1
			m1 = i
		elif a[m2] < a[i]:
			m2 = i
	return (m1, m2)
n = int(input())
a = list(map(int, input().split()))
g = [(i, 1 << n) for i in range(1 << n)]
a += [0]
res = 0
for i in range(n):
	for j in range(1 << n):
		if 1 << i & j:
			g[j] = max2(g[j], g[j ^ 1 << i])
ans = []
for i in range(1, 1 << n):
	res = max(res, a[g[i][0]] + a[g[i][1]])
	ans.append(res)
print(*ans, sep='\n')


n = int(input())
a = list(map(int, input().split()))
m = [[ai] for ai in a]
for d in range(n):
	for s in range(1 << n):
		if s >> d & 1 == 0:
			t = s | 1 << d
			m[t] = sorted(m[t] + m[s])[-2:]
for k in range(1, 1 << n):
	ans = sum(m[k])
	for d in range(n):
		if k >> d & 1 == 1:
			t = k ^ 1 << d | (1 << d) - 1
			ans = max(ans, sum(m[t]))
	print(ans)


import sys
readline = sys.stdin.readline
N = int(readline())
A = list(map(int, readline().split()))
dp = [(a, 0) for a in A]
for i in range(N):
	for j in range(1 << N):
		if not j & 1 << i:
			k = j | 1 << i
			(a, b) = dp[k]
			(c, d) = dp[j]
			res = None
			if a > c:
				if b > c:
					res = (a, b)
				else:
					res = (a, c)
			elif a > d:
				res = (c, a)
			else:
				res = (c, d)
			assert res == tuple(sorted([a, b, c, d], reverse=True)[:2]), ''
			dp[k] = res
dp[0] = sum(dp[0])
for i in range(1, 1 << N):
	dp[i] = max(dp[i - 1], sum(dp[i]))
print('\n'.join(map(str, dp[1:])))


N = int(input())
A = list(map(int, input().split()))
INF = float('inf')
B = [[A[i], -INF] for i in range(1 << N)]
for i in range(N):
	for j in range(1 << N):
		if j & 1 << i:
			tmp = B[j] + B[j ^ 1 << i]
			tmp = sorted(tmp, reverse=True)
			B[j] = tmp[:2]
ans = -INF
for i in range(1, 1 << N):
	ans = max(ans, sum(B[i]))
	print(ans)


(N, d, r) = (int(input()), [], 0)
for a in map(int, input().split()):
	d.append([-a])
for n in range(N):
	B = 1 << n
	for i in range(1 << N):
		if i & B:
			d[i] = sorted(d[i ^ B] + d[i])[:2]
for (a, b) in d[1:]:
	r = min(r, a + b)
	print(-r)


N = int(input())
A = [int(i) for i in input().split()]
C = []
l = 0
C.append([(0, -1), (A[0], 0)])
for i in range(1, 2 ** N):
	(biggest, second) = ((A[i], i), (0, -1))
	for k in range(l + 1):
		if i & 1 << k:
			for a in C[i ^ 1 << k]:
				if a[0] > biggest[0]:
					second = biggest
					biggest = a
				elif a[0] > second[0] and biggest != a:
					second = a
	C.append([second, biggest])
	if i == 2 ** (l + 1) - 1:
		l += 1
ans = [0]
for i in range(1, 2 ** N):
	(a, b) = C[i]
	ans.append(max(ans[-1], a[0] + b[0]))
	print(ans[-1])


def max2(a, b, c, d):
	vals = sorted((a, b, c, d), reverse=True)
	return (vals[0], vals[1])
n = int(input())
a = list(map(int, input().split()))
dp = [[0] * (1 << n) for i in range(n + 1)]
dq = [[0] * (1 << n) for i in range(n + 1)]
for i in range(1 << n):
	dp[0][i] = a[i]
for i in range(n):
	for bit_state in range(1 << n):
		if 1 << i & bit_state:
			(first, second) = max2(dp[i][bit_state], dq[i][bit_state], dp[i][bit_state ^ 1 << i], dq[i][bit_state ^ 1 << i])
		else:
			(first, second) = (dp[i][bit_state], dq[i][bit_state])
		(dp[i + 1][bit_state], dq[i + 1][bit_state]) = (first, second)
ans = 0
for i in range(1, 1 << n):
	ans = max(ans, dp[-1][i] + dq[-1][i])
	print(ans)


import sys

def I():
	return int(sys.stdin.readline().rstrip())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))
N = I()
A = LI()
dp = [[0] * (N + 1) for _ in range(1 << N)]
for i in range(1 << N):
	for j in range(N + 1):
		if j == 0:
			dp[i][j] = A[i]
			continue
		if not i & 1 << j - 1:
			dp[i][j] = dp[i][j - 1]
		else:
			(a, b) = divmod(dp[i][j - 1], 1 << 30)
			(c, d) = divmod(dp[i & ~(1 << j - 1)][j - 1], 1 << 30)
			X = [a, b, c, d]
			X.sort(reverse=True)
			dp[i][j] = (X[1] << 30) + X[0]
ans = 0
for i in range(1, 1 << N):
	(a, b) = divmod(dp[i][-1], 1 << 30)
	ans = max(ans, a + b)
	print(ans)


from itertools import accumulate

def solve(A):

	def keep_max_2(i, j, k):
		if i == k or j == k:
			return (i, j)
		if A[j] > A[k]:
			return (i, j)
		elif A[i] > A[k]:
			return (i, k)
		else:
			return (k, i)
	n = len(A)
	dp0 = [0] * n
	dp1 = [0] * n
	small = min(((a, i) for (i, a) in enumerate(A)))[1]
	for i in range(1, n):
		(x, y) = (i, 0) if A[i] > A[0] else (0, i)
		for d in range(n.bit_length() - 1):
			j = i ^ 1 << d
			if j > i:
				continue
			(x, y) = keep_max_2(x, y, dp0[j])
			(x, y) = keep_max_2(x, y, dp1[j])
		dp0[i] = x
		dp1[i] = y
	return accumulate((A[dp0[i]] + A[dp1[i]] for i in range(1, n)), max)

def __starting_point():
	n = int(input())
	A = tuple(map(int, input().split()))
	print(*solve(A), sep='\n')
__starting_point()


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul
sys.setrecursionlimit(2147483647)
INF = 10 ** 13

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353
n = int(input())
aaa = list(map(int, input().split()))
n2 = 1 << n
dp = [[a, 0] for a in aaa]
for j in range(n):
	b = 1 << j
	for i in range(n2):
		if not i & b:
			(dpi, dpk) = (dp[i], dp[i | b])
			if dpk[0] < dpi[0]:
				dpk[1] = max(dpk[0], dpi[1])
				dpk[0] = dpi[0]
			elif dpk[1] < dpi[0]:
				dpk[1] = dpi[0]
ans = []
tmp = 0
for a in dp[1:]:
	tmp = max(tmp, a[0] + a[1])
	ans.append(tmp)
print(*ans)


def upd(now, x):
	if now[0] < x:
		now = [x, now[0]]
	elif now[1] < x:
		now[1] = x
	return now

def update(now, next):
	ary = now + next
	ary.sort(reverse=True)
	return ary[:2]

def main(n, a):
	dp = [[a[i], 0] for i in range(2 ** n)]
	now = a[0]
	for j in range(n):
		bit = 1 << j
		for i in range(1 << n):
			if i & bit == 0:
				dp[i | bit] = update(dp[i], dp[i ^ bit])
	now = sum(dp[0])
	for k in range(1, 2 ** n):
		now = max(now, sum(dp[k]))
		print(now)
n = int(input())
a = list(map(int, input().split()))
main(n, a)


N = int(input())
A = list(map(int, input().split()))
A = [[a, 0] for a in A]
step = 1
for _ in range(N):
	step *= 2
	for s in range(2 ** N):
		if s // (step // 2) % 2 == 0:
			continue
		tmp = A[s] + A[s - step // 2]
		tmp.sort()
		A[s] = [tmp[-1], tmp[-2]]
tmp = 0
for s in range(1, 2 ** N):
	tmp = max(tmp, sum(A[s]))
	print(tmp)


N = int(input())
A = list(map(int, input().split())) + [0]
data = [[] for i in range(2 ** N)]
for i in range(1, 2 ** N):
	for j in range(N):
		if i & 1 << j == 0:
			continue
		else:
			data[i].append(i - (1 << j))
MAX = [0] * 2 ** N
semiMAX = [0] * 2 ** N
semiMAX[0] = 2 ** N
if MAX[0] < A[1]:
	MAX[1] = 1
	semiMAX[1] = 0
else:
	MAX[1] = 0
	semiMAX[1] = 1
K = [A[0] + A[1]]
for k in range(2, 2 ** N):
	(a, b) = (k, 2 ** N)
	for u in data[k]:
		(c, d) = (MAX[u], semiMAX[u])
		if A[c] <= A[b]:
			c = c
		elif A[d] >= A[a]:
			(a, b) = (c, d)
		elif A[c] > A[a]:
			(a, b) = (c, a)
		elif A[a] >= A[c] > A[b] and a != c:
			b = c
		elif A[a] >= A[d] > A[b] and a != d:
			b = d
	MAX[k] = a
	semiMAX[k] = b
	K.append(max(K[-1], A[a] + A[b]))
for u in K:
	print(u)


import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
dp = [[A[S], 0] for S in range(1 << N)]
for k in range(N):
	for S in range(1 << N):
		if S >> k & 1:
			if dp[S][0] < dp[S ^ 1 << k][0]:
				dp[S][1] = max(dp[S][0], dp[S ^ 1 << k][1])
				dp[S][0] = dp[S ^ 1 << k][0]
			else:
				dp[S][1] = max(dp[S][1], dp[S ^ 1 << k][0])
ans = 0
for K in range(1, 1 << N):
	ans = max(ans, sum(dp[K]))
	print(ans)


n = int(input())
a = list(map(int, input().split()))
dp = [[0, 0] for i in range(1 << n)]

def merge(ls1, ls2):
	(p, q) = ls1
	(r, s) = ls2
	ret = [max(p, r)]
	if p > r:
		ret.append(max(q, r))
	else:
		ret.append(max(p, s))
	return ret
for i in range(1 << n):
	dp[i][0] = a[i]
for i in range(n):
	for j in range(1 << n):
		if 1 << i & j:
			dp[j] = merge(dp[j], dp[1 << i ^ j])
ans = [0 for i in range(2 ** n)]
for i in range(1, 1 << n):
	ans[i] = max(ans[i - 1], sum(dp[i]))
for i in ans:
	if i:
		print(i)


(N, *A) = map(int, open(0).read().split())
(A, r, R) = ([[a] for a in A], 0, range)
for n in R(N):
	B = 1 << n
	for i in R(1 << N):
		if i & B:
			A[i] = sorted(A[i ^ B] + A[i])[-2:]
for (a, b) in A[1:]:
	r = max(r, a + b)
	print(r)


N = int(input())
A = [int(i) for i in input().split()]
B = [[A[i], -10 ** 15] for i in range(2 ** N)]
for i in range(N):
	for b in range(2 ** N):
		if 1 & b >> i == 1:
			merge = B[b] + B[b ^ 1 << i]
			merge.sort(reverse=True)
			B[b] = merge[:2]
ans = -10 ** 15
for i in range(1, 2 ** N):
	ans = max([ans, sum(B[i])])
	print(ans)