You are organizing a boxing tournament, where $n$ boxers will participate ($n$ is a power of $2$), and your friend is one of them. All boxers have different strength from $1$ to $n$, and boxer $i$ wins in the match against boxer $j$ if and only if $i$ is stronger than $j$.

The tournament will be organized as follows: $n$ boxers will be divided into pairs; the loser in each pair leaves the tournament, and $\frac{n}{2}$ winners advance to the next stage, where they are divided into pairs again, and the winners in all pairs advance to the next stage, and so on, until only one boxer remains (who is declared the winner).

Your friend really wants to win the tournament, but he may be not the strongest boxer. To help your friend win the tournament, you may bribe his opponents: if your friend is fighting with a boxer you have bribed, your friend wins even if his strength is lower.

Furthermore, during each stage you distribute the boxers into pairs as you wish.

The boxer with strength $i$ can be bribed if you pay him $a_i$ dollars. What is the minimum number of dollars you have to spend to make your friend win the tournament, provided that you arrange the boxers into pairs during each stage as you wish?


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 2^{18}$) — the number of boxers. $n$ is a power of $2$.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$, where $a_i$ is the number of dollars you have to pay if you want to bribe the boxer with strength $i$. Exactly one of $a_i$ is equal to $-1$ — it means that the boxer with strength $i$ is your friend. All other values are in the range $[1, 10^9]$.


-----Output-----

Print one integer — the minimum number of dollars you have to pay so your friend wins.


-----Examples-----
Input
4
3 9 1 -1

Output
0
Input
8
11 -1 13 19 24 7 17 5

Output
12


-----Note-----

In the first test case no matter how you will distribute boxers into pairs, your friend is the strongest boxer and anyway wins the tournament.

In the second test case you can distribute boxers as follows (your friend is number $2$):

$1 : 2, 8 : 5, 7 : 3, 6 : 4$ (boxers $2, 8, 7$ and $6$ advance to the next stage);

$2 : 6, 8 : 7$ (boxers $2$ and $8$ advance to the next stage, you have to bribe the boxer with strength $6$);

$2 : 8$ (you have to bribe the boxer with strength $8$);

Difficulty: interview

Starter code:

Solutions:
from heapq import heappush, heappop
N = int(input())
A = [int(a) for a in input().split()]
for i in range(N):
    if A[i] < 0:
        k = i
        break
A = [0] + [0 if i < k else A[i] for i in range(N) if i != k]

ans = A.pop()
H = []
while N > 2:
    N //= 2
    for i in range(N):
        heappush(H, A.pop())
    ans += heappop(H)

print(ans)




import sys
from heapq import heappop, heappush
from math import log2


# inf = open('input.txt', 'r')
# reader = (map(int, line.split()) for line in inf)
reader = (list(map(int, s.split())) for s in sys.stdin)

def bribe(n, a):
    if a[-1] < 0:
        return 0
    
    fr = a.index(-1)
    a[fr] = float('inf')
    h = int(log2(n))
    k = int(log2(fr + 1))
    total = a[-1]
    hq = []
    for r in range(h - 1, k, -1):
        [heappush(hq, a[i]) for i in range(2 ** r - 1, 2 ** (r + 1) - 1)];
        opponent = heappop(hq)
        total += opponent
    return total

n, = next(reader)
a = list(next(reader))
ans = bribe(n, a)
print(ans)
    
# inf.close()


import sys
input = sys.stdin.readline

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

x=A.index(-1)
for i in range(x+1):
    A[i]=0
B=list(reversed(A))
import heapq
H=[]

ANS=0
LIST=[0]+[n-(1<<i)+1 for i in range(n.bit_length()-1,0,-1)]
for i in range(1,n.bit_length()):
    for j in range(LIST[i-1],LIST[i]):
        heapq.heappush(H,B[j])

    #print(H)

    x=heapq.heappop(H)
    ANS+=x

print(ANS)
        
        
    


from heapq import *

n = int(input())

a = list(map(int, input().split()))
done = a.index(-1)

heap = []

cost = 0
x = n//2
position = n-1
while position > done:
    highest = a[position]
    he = min(heap) if heap else 10**10
    
    if highest < he:
        cost += highest
        for val in a[position-1:position-x:-1]:
            heappush(heap, val)
        position -= x
    else:
        cost += he
        heappop(heap)
        for val in a[position:position-x:-1]:
            heappush(heap, val)
        position -= x
    x //= 2
    
print(cost)


from sys import stdin

input = stdin.readline

n = int(input())

a = list(map(int, input().split()))
a.reverse()

inf = float('inf')
N = 19
dp = [[inf] * (N+2) for _ in range(1 << N)]

sum = [0] * (1 << 21)
now = n
for i in range(1, 20):
    sum[i] = sum[i-1] + now // 2
    now //= 2


for i in range(n)[::-1]:
    for j in range(N):
        if a[i] == -1:
            dp[i][j] = 0
            continue

        if i > sum[j]:
            continue
        dp[i][j] = dp[i + 1][j + 1] + a[i]
        if i < sum[j]:
            dp[i][j] = min(dp[i][j], dp[i + 1][j])
        # print(i, j, dp[i][j])

print(dp[0][0])

import math
import sys
from sys import stdin, stdout

#sys.setrecursionlimit(300000)
# print(sys.getrecursionlimit())

# dp O(NlogN)
def getMinimunCost(a, sum, i, j, dp):

    if dp[i][j] != -1:
        return dp[i][j]

    if a[j] == -1:
        return 0

    remaining = sum[i] - j

    res = -2
    if i < len(dp)-1:
        min1 = getMinimunCost(a, sum, i+1, j+1, dp)
        if min1 != -2:
            res = min1 + a[j]

    if remaining > 0:
        min2 = getMinimunCost(a, sum, i, j+1, dp)
        if res == -2:
            res = min2
        elif min2 != -2:
            res = min(res, min2)

    dp[i][j] = res
    return dp[i][j]

def getMinimunCost2(a, sum, dp):

    if a[0] == -1:
        for j in range(0, len(dp[0])):
            dp[0][j] = 0
    else:
        for j in range(0, len(dp[0])):
            dp[0][j] = a[0]

    for i in range(1, len(dp)):
        for j in range(1, len(dp[i])):
            if j <= sum[i]:
                if j > 0:
                    dp[i][j] = min(dp[i][j], dp[i][j-1])
                    if i > 0:
                        dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + a[j])
            else:
                dp[i][j] = min(dp[i][j], dp[i][j-1])
                #break;

    #for i in range(len(dp)):
    #    print(dp[i])

    #print(a)

    return dp[-1][-1]


def __starting_point():
    try:
        n = int(stdin.readline())
        a = [int(i) for i in stdin.readline().split()]

        bcnt = int(math.log(n, 2))

        sum = []
        sum.append(0)

        x = int(n/2)
        for i in range(1, bcnt+1):
            sum.append(sum[i-1] + x)
            x = int(x/2)

        #dp = [[-1 for i in range(n)] for i in range(bcnt + 1)]
        dp = [[float("inf") for i in range(n)] for i in range(bcnt + 1)]

        #print(sum)
        #print(str(dp[0][0] + 1))

        #set 0
        flag = True
        for i in range(len(a)):
            if a[i] == -1:
                flag = False
                a[i] = 0
            if flag:
                a[i] = 0

        a.reverse()
        #res = getMinimunCost(a, sum, 0, 0, dp)
        res = getMinimunCost2(a, sum, dp)

        stdout.write(str(res))
    except BaseException as e:
        print(str(e))

__starting_point()

from heapq import heappush, heappop
N = int(input())
A = [int(a) for a in input().split()]
for i in range(N):
    if A[i] < 0:
        k = i
        break
A = [0] + [0 if i < k else A[i] for i in range(N) if i != k]
 
ans = A.pop()
H = []
while N > 2:
    N //= 2
    for i in range(N):
        heappush(H, A.pop())
    ans += heappop(H)
 
print(ans)
 


from heapq import heappush, heappop
N = int(input())
A = [int(a) for a in input().split()]
for i in range(N):
    if A[i] < 0:
        k = i
        break
A = [0] + [0 if i < k else A[i] for i in range(N) if i != k]
 
ans = A.pop()
H = []
while N > 2:
    N //= 2
    for i in range(N):
        heappush(H, A.pop())
    ans += heappop(H)
 
print(ans)
 


from math import log2, floor

def is_power2(num):
    return num != 0 and ((num & (num - 1)) == 0)


def next_two_pow(val):
    pw=0
    while 2**pw <= val:
        pw=+1
    return pw        

n = int(input())
arr=[int(x) for x in input().split()]


win_idx =-1
selected=[]

for i in range(1,n+1):
    val = arr[i-1]
    if win_idx ==-1:
       if  val == -1: 
           win_idx =i
    else:
         if is_power2(i):
             selected.append(val)
             selected.sort()
         else:
             if len(selected) > 0 and val < selected[-1]:
                 selected.pop()
                 selected.append(val)
                 selected.sort()

print(sum(selected))


# if arr[n-1] ==-1:
#     print(0)
# else:
#     win_idx =-1
#     for i in range(0,n):
#         if arr[i] == -1:
#             win_idx =i
#             break
# 
#     crt_pow=int(floor(log2(n)))
#     stop_pow=next_two_pow(win_idx)
#     total=0
#     taken= set()
#     while crt_pow > stop_pow:
#         two_p = 2**crt_pow
#         mn = 10**9 + 1
#         mn_idx = -1
#         for i in range(two_p - 1, n):
#             if i!=win_idx and i not in taken and  arr[i] < mn:
#                 mn =arr[i]
#                 mn_idx=i
#         crt_pow -=1        
#         taken.add(mn_idx)
#         total+=mn
#     print(total)    


from math import log2, floor

def is_power2(num):
    return num != 0 and ((num & (num - 1)) == 0)


def next_two_pow(val):
    pw=0
    while 2**pw <= val:
        pw=+1
    return pw        

n = int(input())
arr=[int(x) for x in input().split()]


win_idx =-1
selected=[]

for i in range(1,n+1):
    val = arr[i-1]
    if win_idx ==-1:
       if  val == -1: 
           win_idx =i
    else:
         if is_power2(i):
             selected.append(val)
             selected.sort()
         else:
             if len(selected) > 0 and val < selected[-1]:
                 selected.pop()
                 selected.append(val)
                 selected.sort()

print(sum(selected))


# if arr[n-1] ==-1:
#     print(0)
# else:
#     win_idx =-1
#     for i in range(0,n):
#         if arr[i] == -1:
#             win_idx =i
#             break
# 
#     crt_pow=int(floor(log2(n)))
#     stop_pow=next_two_pow(win_idx)
#     total=0
#     taken= set()
#     while crt_pow > stop_pow:
#         two_p = 2**crt_pow
#         mn = 10**9 + 1
#         mn_idx = -1
#         for i in range(two_p - 1, n):
#             if i!=win_idx and i not in taken and  arr[i] < mn:
#                 mn =arr[i]
#                 mn_idx=i
#         crt_pow -=1        
#         taken.add(mn_idx)
#         total+=mn
#     print(total)    


def main():
    import sys
    from operator import itemgetter
    input = sys.stdin.readline

    N = int(input())
    K = N.bit_length() - 1
    A_raw = list(map(int, input().split()))

    flg = 1
    A = []
    for i, a in enumerate(A_raw):
        if flg:
            if a == -1:
                flg = 0
            else:
                A.append(0)
        else:
            A.append(A_raw[i])
    inf = 1<<40
    dp = [[inf] * (K+1) for _ in range(N)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(K+1):
            if dp[i][j] < inf:
                if j < K:
                    dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + A[N-2-i])
                if N - 2**(K-j) > i:
                    dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    print(dp[-1][-1])


def __starting_point():
    main()
__starting_point()

n = int(input())
a = list(map(int, input().split()))
me = a.index(-1)
if me == n - 1:
    print(0)
    return
for i in range(me + 1):
    a[i] = 0
dp = [[0] * n for _ in range(2)]
opt = [[0] * n for _ in range(2)]
dp[1][n - 1] = a[n - 1]
if n - 1 <= me + 1:
    ans = a[n - 1]
for i in range(2, 22):
    if 2 ** i > n:
        break
    s = i & 1
    t = s ^ 1
    l, r = n // 2 ** (i - 1) - 1, n - i + 1
    pl, pr = n // 2 ** (i - 2) - 1, n - i + 2
    opt[s][pr - 1] = dp[t][pr - 1]
    for j in range(pr - 2, pl - 1, -1):
        opt[s][j] = min(opt[s][j + 1], dp[t][j])
    for j in range(pl - 1, l - 1, -1):
        opt[s][j] = opt[s][j + 1]
    for j in range(r - 1, l - 1, -1):
        dp[s][j] = opt[s][j + 1] + a[j]
    if l <= me + 1:
        ans = min(dp[s][l:r])
print(ans)

import sys
input = sys.stdin.readline
import heapq as hq
n = int(input())
a = list(map(int,input().split()))
frn = a.index(-1)+1
t = n.bit_length()
if frn == n:
  print(0)
  return
ans = a[n-1]
x = (frn-1).bit_length()
q = []
hq.heapify(q)
for i in range(1,t)[::-1]:
  for j in range(2**(i-1)-1,2**i-1):
    hq.heappush(q,a[j])
  y = hq.heappop(q)
  if y >= 0:
    ans += y
  else:
    break
print(ans)

import heapq
 
pop=heapq.heappop
push=heapq.heappush
 
n=int(input())
a=list(map(int, input().split()))
 
ans=0
pos=-1
 
for i, x in enumerate(a):
    if x==-1:
        pos=i
        break
        
if pos==n-1:
    print(0)
else:
    ans += a[n-1]
    cur  = n-2
    
    used      = [0] * n 
    used[pos] = 1
    used[n-1] = 1
    
    Q=[]
    i=n//2
    
    
    while i>=2:
        for _ in range(i):
            while used[cur]==1:
                cur-=1
            
            val=0 if cur < pos else a[cur]
            push(Q, (val, cur))
            cur-=1
            
        while True:
            x, p = pop(Q)
            
            if used[p]==0:
                break
                
        used[p]=1
        #print(p, a[p])    
        if p > pos:
            ans+=a[p]
        i//=2        
        
    print(ans)