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

Starter code:

Solutions:
j=n=1<<int(input())
a=[[0,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)

# -*- coding:utf-8 -*-
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)

import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
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
    ans = []
    for i in range(1, 1 << n):
        res = max(res, sum(f[i]))
        ans.append(res)
    print('\n'.join(map(str, ans)))
resolve()

#!/usr/bin/env python

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

    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)
    #print(P)

func()

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

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

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

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)

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]
            else:
                if(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()))

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)]
			else:
				if 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 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


def __starting_point():
    main()


__starting_point()

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

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)

#!/usr/bin/env python

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

    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)
    #print(P)

func()

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
input = sys.stdin.readline
from itertools import accumulate

def merge(x, y):
  D = sorted([dp[x][0], dp[x][1], dp[y][0], dp[y][1]], reverse=True)
  return (D[0], D[1])
  
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")

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)]
#print(dp)
for i in range(N):
    for j in range(1<<N):
        if j & (1<<i):
            #print(j,i,j|(1<<i))
            dp[j]=chmax(dp[j],dp[j^(1<<i)])
#print(dp)
ans =sum(dp[0])
for i in range(1,1<<N):
    t = sum(dp[i])
    ans = max(ans,t)
    print(ans)

N = int(input())
A = list(map(int, input().split()))
 
#dp[S] = A[S], -inf で初期化　Sの部分集合TのうちA[T]が(最大のもの, 次に大きいもの)　を入れていく
 
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: # Tがiを含むとき
            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)

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


from itertools import accumulate

def zeta(data, merge):
    """
    （この関数はdataを上書きします）
    Mはモノイド
    data: 2^n -> M
    output: 2^n -> M
    merge: M -> M
 
    ouput[i] = sum(data[j] for j in range(2^n) if i|j == i)
    """
    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()

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]
        self.s=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)



"""

https://atcoder.jp/contests/arc100/tasks/arc100_c

情報を再利用するのがメイン
K=Xの時は,K=X-1の時の答えに加え、 i or j == K の場合を考えればいい
or がKとなる場合、0の桁は両方0で、1の桁は片方が1ならよい
1では3通りの分け方があるので、3^N…

大きいほうから考えてみる？
最後は、当然最大のやつ2個→その2つのindex のORまではそれが保持

dp[X] = X と orしてもXのままのindexの集合における最大 & 2番目
→とすれば、1の桁全てに関して0にしてみた奴とXを見れば推移できる

O(2^N * logMAX(A)) で解けそうだ

"""

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

    #print (i,na,nb)
    ans = max(A[na] + A[nb] , ans)
    aaa.append(ans)
    dp.append( ( na,nb ) )

print(("\n".join(map(str,aaa))))


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)

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

N = int(input())
A = [(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(N):
    ii = 1 << i
    for j in range(1<<N)[::-1]:
        if j & ii:
            A[j] = combine(A[j], A[j^ii])

ANS = [0] * (1<<N)
for i in range(1, 1<<N):
    ANS[i] = max(ANS[i-1], sum(A[i]))

print("\n".join(map(str, ANS[1:])))

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)

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


import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
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()

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)


N,r,d=int(input()),0,[[int(s)] for s in input().split()]
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=max(r,a+b);print(r)

import sys

sys.setrecursionlimit(10 ** 6)
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]
        self.s=x+y

    def __add__(self, other):
        i=j=0
        self.val=sorted(self.val+other.val,reverse=True)[:2]
        self.s=sum(self.val)
        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,int(dp[j].s))
    print(mx)


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)]
#print(dp)
for i in range(N):
    for j in range(1<<N):
        if (j & (1<<i))==0:
            #print(j,i,j|(1<<i))
            dp[j|(1<<i)]=chmax(dp[j],dp[j|(1<<i)])
#print(dp)
ans =sum(dp[0])
for i in range(1,1<<N):
    t = sum(dp[i])
    ans = max(ans,t)
    print(ans)

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)

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)


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)

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)

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


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


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

def main1(n,a):
    # 1<=k<=2^n-1
    # O(n*2^n)
    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)
#num0=main0(n,a)
#print(*num1,sep='\n')
#print(*num0,sep=' ')


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

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)



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


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)
    
    """
    下位集合に対する高速ゼータ変換．
    (Kがi,jを包含している）
    ここでのgを適切なfの和として考えるのが基本だけど，
    今回は和ではなくて上位2つの要素を持つ
    """
    
    g=[[0,0]for _ in range(N2)]
    
    for i in range(N2):
        g[i][0]=A[i]
        
    for k in range(N):#このkはKと違う，kbit目に着目する
        for s in range(N2):#これが今回でいうK，
            if ((s>>k)&1):#sのkbit目が立っていれば
                #加法として，上位2つを選択する
                L=[0,0,0,0]
                L[0]=g[s][0]
                L[1]=g[s][1]
                L[2]=g[(s^(1<<k))][0]#sのkbit目をマスクしたgを持ってくる
                L[3]=g[(s^(1<<k))][1]
                L.sort()
                g[s][0]=L[-1]
                g[s][1]=L[-2]
                #print(bin(s),k,g[s],L)
                
    ans=0
    for k in range(1,N2):
        ans=max(ans,sum(g[k]))
        print(ans)
        
    
                    
                
            
        
    
    

main()


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)]
  #dp[0][0]=a[0]
  now=a[0]
  for j in range(n):
    bit=1<<j
    for i in range(1<<n):
      if i&bit==0:
        # i|bit:iを部分集合として含む数字
        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()))
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)


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)


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

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)


# coding: utf-8
# Your code here!
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:]

#print(top2)

ans = list(map(sum,top2))

for i in range(1,1<<n):
    ans[i] = max(ans[i],ans[i-1])
    print((ans[i]))




from itertools import accumulate

def solve(A):
    def keep_max_2(i,j,k):
        if i == k or j == k:
            return i,j
        # A[i] > A[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()

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))
        else:
            if com[0][1] < com[1][1]:
                if com[0][1] < val:
                    com[0] = (ind, val)
                elif com[1][1] < val:
                    com[1] = (ind, val)
            else:
                if 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)

#!/usr/bin/env python

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)
    #print(P)

func()

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

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

A = [[a, 0] for a in A]
#print(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()
    #print(s, tmp, s, s-step//2)
    A[s] = [tmp[-1], tmp[-2]]
#print(A)
tmp = 0
for s in range(1,2**N):
  tmp = max(tmp, sum(A[s]))
  print(tmp)


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

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n = int(input()) 
#n,x = [int(i) for i in readline().split()]
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

#print(a)
za = zeta_transform(a[:],n)
#print(zeta_transform(a[:],n),"zeta-a")

for i, zi in enumerate(za):
    if not i: ans = 0
    else:
        i1,i2 = za[i]
        ans = max(ans,i1+i2)
        print(ans)    




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 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(len(bin(i))-2):
            t5, t6, t7, t8 = d[i & ~(1 << j)]
            if t5 > t1:
                t1, t2, t3, t4 = t5, t6, t1, t2
            elif t5 > t3:
                if t6 != t2:
                    t3, t4 = t5, t6
                    continue
            if t7 > t3:
                t3, t4 = t7, t8
        d[i] = [t1, t2, t3, t4]
        ans = max(ans, t1+t3)
        print(ans)


main()

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)

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

j=n=1<<int(input())
a=[[int(s)]for s in input().split()]
while~-j: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,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)

#!/usr/bin/env python

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

    for i in range(1, 2 ** N):
        Ai = A[i]
        Pi = P[i]
        if (Ai, i) > Pi[0]:
            Pi[1] = Pi[0]
            Pi[0] = (Ai, i)
        elif (Ai, i) > Pi[1]:
            Pi[1] = (Ai, i)
        for j in range(N):
            if (i & (1 << j)) == 0:
                Pindex = P[i + (1 << j)]
                for k in range(2):
                    if Pi[k] > Pindex[0]:
                        Pindex[1] = Pindex[0]
                        Pindex[0] = Pi[k]
                    elif Pi[k] > Pindex[1] and Pi[k] != Pindex[0]:
                        Pindex[1] = Pi[k]
    ans = 0
    for i in range(1, 2 ** N):
        ans = max(ans, P[i][0][0] + P[i][1][0])
        print(ans)
    #print(P)

func()

#!/usr/bin/env python

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

    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)
    #print(P)

func()

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 = 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]:  # skip dp[0][i] == elem
        dp[1][i] = elem
        return True
    else:
        return False


dp = [[0] * len(As) for _ in range(2)]  # first largest and second largest
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)


import sys
input = sys.stdin.readline
from heapq import heappushpop

N = int(input())
A = [int(x) for x in input().split()]

# B_x = max {A_y | y\subset x}
# と思ったが、2元ずつ持つ必要がある。
# (値、何番から来たか)
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:]))))



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)
            else:
                if 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:])))

from itertools import accumulate

def zeta(data, merge):
    """
    （この関数はdataを上書きします）
    Mはモノイド
    data: 2^n -> M
    output: 2^n -> M
    merge: M -> M
 
    ouput[i] = sum(data[j] for j in range(2^n) if i|j == i)
    """
    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 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()

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

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)

from sys import stdin
readline = stdin.readline

n = int(readline())

a = list(map(int, readline().split()))
k_max = 1 << n

# 和が最大 => 最大、2番目に大きいものの和
# dp[k] == kを得るときの最大、2番目に大きいもの
# == max(dp[i] | i はkの部分集合)
# kの部分集合は k に1要素足りないものを列挙すれば十分。
# (2要素以上足りないものは1要素足りないものの部分集合なので)
dp = [[a[i], 0] for i in range(k_max)]
for i in range(n):
    bit = (1 << i)  # i bit目に着目
    for src in range(k_max):  # i bit目が0のものからibit目が1のものへ配るDP
        if bit & src:
            continue  # すでにi bit目が1なら無視
        dst = bit | src
        max_values = dp[dst] + dp[src]
        max_values.sort()
        dp[dst] = [max_values[-1], max_values[-2]]

# k以下 => 前回の答え(k未満)とkに等しい時を合わせた結果
ans = 0
for k in range(1, k_max):
    ans = max(ans, dp[k][0] + dp[k][1])
    print(ans)


from itertools import accumulate

def zeta(data, merge):
    """
    （この関数はdataを上書きします）
    Mはモノイド
    data: 2^n -> M
    output: 2^n -> M
    merge: M -> M
 
    ouput[i] = sum(data[j] for j in range(2^n) if i|j == i)
    """
    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 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)