Om Nom is the main character of a game "Cut the Rope". He is a bright little monster who likes visiting friends living at the other side of the park. However the dark old parks can scare even somebody as fearless as Om Nom, so he asks you to help him. [Image] 

The park consists of 2^{n} + 1 - 1 squares connected by roads so that the scheme of the park is a full binary tree of depth n. More formally, the entrance to the park is located at the square 1. The exits out of the park are located at squares 2^{n}, 2^{n} + 1, ..., 2^{n} + 1 - 1 and these exits lead straight to the Om Nom friends' houses. From each square i (2 ≤ i < 2^{n} + 1) there is a road to the square $\lfloor \frac{i}{2} \rfloor$. Thus, it is possible to go from the park entrance to each of the exits by walking along exactly n roads.  [Image]  To light the path roads in the evening, the park keeper installed street lights along each road. The road that leads from square i to square $\lfloor \frac{i}{2} \rfloor$ has a_{i} lights.

Om Nom loves counting lights on the way to his friend. Om Nom is afraid of spiders who live in the park, so he doesn't like to walk along roads that are not enough lit. What he wants is that the way to any of his friends should have in total the same number of lights. That will make him feel safe. 

He asked you to help him install additional lights. Determine what minimum number of lights it is needed to additionally place on the park roads so that a path from the entrance to any exit of the park contains the same number of street lights. You may add an arbitrary number of street lights to each of the roads.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10) — the number of roads on the path from the entrance to any exit.

The next line contains 2^{n} + 1 - 2 numbers a_2, a_3, ... a_2^{n} + 1 - 1 — the initial numbers of street lights on each road of the park. Here a_{i} is the number of street lights on the road between squares i and $\lfloor \frac{i}{2} \rfloor$. All numbers a_{i} are positive integers, not exceeding 100.


-----Output-----

Print the minimum number of street lights that we should add to the roads of the park to make Om Nom feel safe.


-----Examples-----
Input
2
1 2 3 4 5 6

Output
5



-----Note-----

Picture for the sample test. Green color denotes the additional street lights. [Image]

Difficulty: MEDIUM
Tags: Graph traversal

Implementation

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
ans = []

def DFS(x, n):
	count = 0
	stack = [(x, count)]
	leaf = 0
	ans = 0
	max1 = 0
	back_stack = []
	points = [0 for i in range(n + 1)]
	while len(stack):
		(temp, count) = stack.pop()
		back_stack.append(temp)
		if 2 * temp >= n:
			continue
		for j in range(2):
			stack.append((2 * temp + j, count + l[2 * temp + j - 2]))
			points[2 * temp + j] = count + l[2 * temp + j - 2]
	while len(back_stack):
		temp = back_stack.pop()
		if 2 * temp >= n:
			continue
		ans = ans + abs(points[2 * temp] - points[2 * temp + 1])
		if points[2 * temp] > points[2 * temp + 1]:
			points[2 * temp + 1] = points[2 * temp]
		else:
			points[2 * temp] = points[2 * temp + 1]
		points[temp] = points[2 * temp]
	return ans
n = int(input())
l = list(map(int, input().split()))
visited = [0 for i in range(2 ** (n + 1))]
x = 1
print(DFS(x, 2 ** (n + 1)))


def dfs(i):
	if i >= 2 ** n:
		return (0, 0)
	(x1, m1) = dfs(i * 2)
	(x2, m2) = dfs(i * 2 + 1)
	if m1 + a[i * 2] < m2 + a[i * 2 + 1]:
		return (x1 + x2 + m2 + a[i * 2 + 1] - m1 - a[i * 2], m2 + a[i * 2 + 1])
	return (x1 + x2 + m1 + a[i * 2] - m2 - a[i * 2 + 1], m1 + a[i * 2])
n = int(input())
a = [0, 0] + [int(i) for i in input().split()]
print(dfs(1)[0])


n = int(input())
l = list(map(int, input().split()))
l = [0] + l
top = 1
lim = 2 ** (n + 1) - 1
count = 0

def solver(top):
	global count
	left = top * 2 + 1
	right = 2 + top * 2
	if left > lim or right > lim:
		return l[top]
	else:
		ll = solver(left)
		rr = solver(right)
		if ll != rr:
			count += max(ll, rr) - min(ll, rr)
		return max(ll, rr) + l[top]
solver(0)
print(count)


n = 2 ** (int(input()) + 1) - 1
a = [0, 0] + list(map(int, input().split()))
r = 0
while n > 1:
	a[n // 2] += max(a[n], a[n - 1])
	r += abs(a[n] - a[n - 1])
	n -= 2
print(r)


n = int(input())
ai = list(map(int, input().split()))
ai = [0, 0] + ai
cnt = []
ans = 0
while n >= 1:
	for i in range(2 ** n, 2 ** (n + 1), 2):
		ans += abs(ai[i] - ai[i + 1])
		ai[i // 2] += max(ai[i], ai[i + 1])
	n -= 1
print(ans)


n = int(input())
a = input().split()
a = [int(i) for i in a]

def solve(n, a, added):
	last = a[-2 ** n:]
	neww = []
	for i in range(0, 2 ** n - 1, 2):
		x = last[i]
		y = last[i + 1]
		neww.append(max(x, y))
		added = added + abs(x - y)
	a = a[:-2 ** n]
	if a == []:
		a = [0]
	for i in range(1, 2 ** (n - 1) + 1):
		a[-i] = a[-i] + neww[-i]
	n = n - 1
	if n == 0:
		print(added)
	else:
		solve(n, a, added)
solve(n, a, 0)


from math import floor

def main():
	n = int(input())
	a = list(map(int, input().split()))
	streets = []
	for i in range(2 ** n, 2 ** (n + 1)):
		idx = i
		if idx > 1:
			res = a[idx - 2]
		while idx > 0:
			idx = int(floor(idx / 2))
			if idx > 1:
				res += a[idx - 2]
		streets.append(res)
	res = 0
	while len(streets) > 2:
		new_streets = []
		for i in range(0, len(streets), 2):
			res += abs(streets[i] - streets[i + 1])
			new_streets.append(max(streets[i], streets[i + 1]))
		streets = new_streets
	print(res + abs(streets[0] - streets[1]))
main()


def balance(node):
	if node >= 2 ** n:
		return 0
	else:
		c1 = balance(2 * node)
		c2 = balance(2 * node + 1)
		a = abs(tree[2 * node - 2] + c1 - tree[2 * node - 1] - c2)
		tree[2 * node - 2] += c1
		tree[2 * node - 1] += c2
		global count
		count += a
		if tree[2 * node - 2] > tree[2 * node - 1]:
			tree[2 * node - 1] += a
		elif tree[2 * node - 2] < tree[2 * node - 1]:
			tree[2 * node - 2] += a
		return tree[2 * node - 1]
n = int(input())
s = input()
s = s.split()
tree = [int(i) for i in s]
count = 0
balance(1)
print(count)


n = int(input())
a = [-1]
a.extend(list(map(int, input().split())))
ans = 0
i = len(a) - 1
while i > 1:
	ans += abs(a[i] - a[i - 1])
	a[i // 2 - 1] += max(a[i], a[i - 1])
	i -= 2
print(ans)


n = int(input())
a = list(map(int, input().split()))
dp = [0] * (2 ** (n + 1) - 1)
for i in range(2, 2 ** (n + 1)):
	dp[i - 1] = dp[i // 2 - 1] + a[i - 2]
mx = 0
sm = 0
x = [0] * (2 ** (n + 1) - 1)
for i in range(2 ** n):
	mx = max(mx, dp[-i - 1])
	sm += dp[-i - 1]
for i in range(2 ** n):
	x[-i - 1] = mx - dp[-i - 1]
i = len(x) - 1
while i >= 0:
	mn = min(x[i], x[i - 1])
	x[i] -= mn
	x[i - 1] -= mn
	x[(i + 1) // 2 - 1] += mn
	i -= 2
print(sum(x))


import math

def add(n, arr):
	sumlis = [i for i in arr]

	def sumdou(i):
		if 2 * i + 2 >= len(arr):
			return arr[i]
		else:
			return sumlis[2 * i + 2] + arr[i]
	tot = 0
	p2 = len(arr)
	for j in reversed(range(n)):
		p1 = p2 - int(math.pow(2, j + 1))
		for i in range(p1, p2, 2):
			s1 = sumdou(i)
			s2 = sumdou(i + 1)
			tot += abs(s2 - s1)
			sumlis[i] = max(s1, s2)
			sumlis[i + 1] = max(s1, s2)
		p2 = p1
	print(tot)
n = int(input())
arr = list(map(int, input().split()))
add(n, arr)


n = int(input())
park = [0] * 2 ** (n + 1)
park[2:2 ** (n + 1)] = [int(i) for i in input().split()]
cnt = 0
for i in range(2 ** n - 1, 0, -1):
	cnt += abs(park[i * 2 + 1] - park[i * 2])
	park[i] += max(park[i * 2 + 1], park[i * 2])
print(cnt)


extra = 0

def func(index, arr):
	global extra
	if index * 2 + 1 >= len(arr):
		return 0
	left = func(index * 2 + 1, arr) + arr[index * 2]
	right = func(index * 2 + 2, arr) + arr[index * 2 + 1]
	if left > right:
		(a, b) = (left, right)
	else:
		(a, b) = (right, left)
	extra = extra + a - b
	return a
n = int(input())
arr = list(map(int, input().split()))
func(0, arr)
print(extra)


from collections import deque
n = int(input())
ligths = [0, 0] + [int(x) for x in input().split()]
prefix_tree = [0 for _ in range(len(ligths))]
q = deque()
q.append(1)
while len(q):
	m = q.pop()
	prefix_tree[m] = ligths[m] + prefix_tree[m // 2]
	if m * 2 + 1 < len(ligths):
		q.append(m * 2)
		q.append(m * 2 + 1)
needed_lights = max(prefix_tree)
suffix_tree = [0 for _ in range(len(ligths))]

def pocitaj(i):
	if i >= len(ligths):
		return
	pocitaj(i * 2)
	pocitaj(i * 2 + 1)
	if i >= len(ligths) // 2:
		suffix_tree[i] = ligths[i]
	else:
		suffix_tree[i] = max(suffix_tree[i * 2], suffix_tree[i * 2 + 1]) + ligths[i]
pocitaj(1)
suffix_tree += [needed_lights for _ in range(len(ligths))]

class Test:

	def __init__(self):
		self.ans = 0
		self.vypocitaj(1)

	def vypocitaj(self, i):
		if suffix_tree[i * 2] < suffix_tree[i * 2 + 1]:
			rozdiel = suffix_tree[i * 2 + 1] - suffix_tree[i * 2]
			self.ans += rozdiel
		else:
			rozdiel = suffix_tree[i * 2] - suffix_tree[i * 2 + 1]
			self.ans += rozdiel
		if i * 2 + 1 < len(ligths):
			self.vypocitaj(i * 2)
			self.vypocitaj(i * 2 + 1)
ans = Test()
print(ans.ans)


import sys, os
import fileinput
n = int(input()) + 1
a = [int(x) for x in input().split()]
all_count = 2 ** n - 1
b = [0] * all_count
counter = 0
for i in range(n, 1, -1):
	lcnt = 2 ** (i - 1)
	first = 2 ** (i - 1) - 2
	level = a[first:first + lcnt]
	for j in range(0, lcnt, 2):
		index = first + 2 + j
		if i == n:
			diff = abs(level[j] - level[j + 1])
			counter += diff
			b[index // 2 - 1] += level[j] + level[j + 1] + diff
		else:
			diff = abs(abs(b[index - 1] // 2 + level[j]) - abs(b[index] // 2 + level[j + 1]))
			counter += diff
			b[index // 2 - 1] += b[index - 1] // 2 + b[index] // 2 + level[j] + level[j + 1] + diff
print(counter)


def get_lights_in_subtree(data, i):
	total = 0
	if i < len(data):
		total += data[i]
	else:
		return 0
	total += get_lights_in_subtree(data, 2 * i + 1)
	total += get_lights_in_subtree(data, 2 * i + 2)
	return total

def count_needed_lights(data, i):
	if i >= len(data):
		return (0, 0)
	l1 = count_needed_lights(data, 2 * i + 1)
	l2 = count_needed_lights(data, 2 * i + 2)
	total = l1[0] + l2[0]
	total += abs(l1[1] - l2[1])
	return (total, max(l1[1], l2[1]) + data[i])
n = int(input())
data = [0] + list(map(int, input().split()))
print(count_needed_lights(data, 0)[0])


n = int(input())
a = [int(x) for x in input().split()]
m = len(a)
sums = [0] * (m + 1)
count = 0
a.insert(0, 0)
add = 0
for i in range(m // 2 - 1, -1, -1):
	m = max(a[2 * i + 1], a[2 * i + 2])
	need_l = m - a[2 * i + 1]
	need_r = m - a[2 * i + 2]
	add += need_l + need_r
	a[i] += a[2 * i + 1] + need_l
print(add)


from operator import itemgetter

def prepare(a, n):
	res = 0
	for i in range(len(a) - 1):
		a[i][1] = a[i // 2 - 1][1] + a[i][0]
	mx = max(a[2 ** n - 2:2 ** (n + 1) - 2], key=itemgetter(1))[1]
	for i in range(2 ** n - 2, 2 ** (n + 1) - 2):
		a[i][1] = mx - a[i][1]
	for i in range(2 ** n - 3, -2, -1):
		mn = a[i][1] = min(a[2 * (i + 1)][1], a[2 * (i + 1) + 1][1])
		res += a[2 * (i + 1)][1] + a[2 * (i + 1) + 1][1] - 2 * mn
	return res

def main():
	n = int(input())
	a = [[int(i), 0] for i in input().split()]
	a += [[0, 0]]
	print(prepare(a, n))
main()


globCnt = 0

def rec(root):
	nonlocal globCnt, cnt
	if root - 1 >= len(cnt):
		return 0
	l = rec(2 * root + 1)
	r = rec(2 * root + 2)
	if l != r:
		globCnt += abs(l - r)
	return max(l, r) + cnt[root - 1]
n = int(input())
cnt = list(map(int, input().split()))
rec(0)
print(globCnt)


n = int(input())
ar = [int(i) for i in input().split()]
tree = []
it = 0
for i in range(n):
	tr = []
	for j in range(it, it + 2 ** (i + 1)):
		tr.append(ar[j])
	tree.append(tr)
	it += 2 ** (i + 1)
add = 0
for i in range(n - 1, 0, -1):
	for j in range(len(tree[i - 1])):
		diff = tree[i][2 * j] - tree[i][2 * j + 1]
		if diff >= 0:
			add += diff
			tree[i - 1][j] += tree[i][2 * j]
		else:
			add -= diff
			tree[i - 1][j] += tree[i][2 * j + 1]
	del tree[i]
diff = tree[0][0] - tree[0][1]
if diff >= 0:
	add += diff
else:
	add -= diff
print(add)


n = int(input())
a = [0] + [0] + list(map(int, input().split()))
ans = 0
for i in range(n, 0, -1):
	for j in range(2 ** i, 2 ** (i + 1), 2):
		lol = max(a[j], a[j + 1])
		ans += abs(a[j] - a[j + 1])
		a[j // 2] += lol
print(ans)


s = 0
n = int(input())
k = (1 << n + 1) - 1
a = [0, 0] + list(map(int, input().split()))
for i in range(k, 1, -2):
	(u, v) = (a[i], a[i - 1])
	if u > v:
		(u, v) = (v, u)
	s += v - u
	a[i >> 1] += v
print(s)


def read_input():
	n = int(input())
	a = [0, 0]
	line = input().strip().split()
	for i in range(2 ** (n + 1) - 2):
		a.append(int(line[i]))
	return (n, a)

def calculate(i, n, a):
	if n == 0:
		c_left = 0
		c_right = 0
	else:
		c_left = calculate(i * 2, n - 1, a)
		c_right = calculate(2 * i + 1, n - 1, a)
	y = a[i] + max(c_left, c_right)
	a[0] += abs(c_left - c_right)
	return y
(n, a) = read_input()
calculate(1, n, a)
print(a[0])


n = int(input())
m = (1 << n + 1) - 1
a = [0] + list(map(int, input().split()))
max_value = 0

def precalc(i, prev):
	nonlocal max_value
	if i < m:
		a[i] += prev
		if a[i] > max_value:
			max_value = a[i]
		precalc((i << 1) + 1, a[i])
		precalc((i << 1) + 2, a[i])

def calc(i):
	if i >= (1 << n) - 1:
		return 0
	x = (i << 1) + 1
	y = (i << 1) + 2
	result = calc(x) + calc(y)
	a[i] = max(a[x], a[y])
	return result + a[i] - min(a[x], a[y])
precalc(0, 0)
print(calc(0))


class Route:

	def __init__(self):
		self.lamps_count = 0
		self.nodes = {}

def solve(n, lamps):
	routes_count = 2 ** n
	max_node_num = 2 ** (n + 1) - 1
	routes = [Route() for _ in range(routes_count)]

	def dfs_pre(node, count=0):
		if node >= routes_count:
			route = routes[node - routes_count]
			route.lamps_count = count
			while node != 0:
				route.nodes[node] = node
				node //= 2
		else:
			dfs_pre(node * 2, count + lamps[(node - 1) * 2])
			dfs_pre(node * 2 + 1, count + lamps[(node - 1) * 2 + 1])

	def dfs_post(node):
		if node > max_node_num:
			return 0
		diffs = []
		for r in routes:
			if node in r.nodes:
				diffs.append(max_lamps_count - r.lamps_count)
		diffs.sort()
		if diffs and diffs[0]:
			for r in routes:
				if node in r.nodes:
					r.lamps_count += diffs[0]
		return diffs[0] + dfs_post(node * 2) + dfs_post(node * 2 + 1)
	dfs_pre(1)
	max_lamps_count = sorted(routes, key=lambda r: -r.lamps_count)[0].lamps_count
	res = dfs_post(1)
	return res

def main():
	n = int(input().strip())
	lamps = list(map(int, input().strip().split()))
	print(solve(n, lamps))
main()


n = int(input())
lst = {i + 1: int(x) for (i, x) in enumerate(input().split())}
lst[0] = 0
x = 2 ** (n + 1) - 1
res = 0
for i in range(n, 0, -1):
	for j in range(x - 1, x - 2 ** i - 1, -2):
		ma = max(lst[j], lst[j - 1])
		mi = min(lst[j], lst[j - 1])
		res += ma - mi
		lst[(j + 1) // 2 - 1] += ma
	x -= 2 ** i
print(res)


n = int(input())
arr = list(map(int, input().split()))
ans = 0
b = 2 ** (n + 1) - 3
while n != 0:
	n -= 1
	p = 2 ** (n + 1) - 3
	while b != p:
		ans += abs(arr[b] - arr[b - 1])
		arr[b // 2 - 1] += max(arr[b], arr[b - 1])
		b -= 2
print(ans)


n = 2 ** (int(input()) + 1) - 1
d = input().split(' ')
for i in range(len(d)):
	d[i] = int(d[i])
p = 0
for i in range(len(d) - 1, 0, -2):
	p += abs(d[i] - d[i - 1])
	d[i // 2 - 1] += max(d[i], d[i - 1])
print(p)


n = int(input())
M = 2 ** (n + 1)
A = [0, 0] + list(map(int, input().split()))
Ans = [0] * M
ans = 0
for i in range(2 ** n - 1, 0, -1):
	left = i * 2
	right = i * 2 + 1
	m_l = A[left] + Ans[left]
	m_r = A[right] + Ans[right]
	Ans[i] = max(m_l, m_r)
	ans += abs(m_l - m_r)
print(ans)


n = int(input())
lis = [0] * 2 + list(map(int, input().split()))
ans = 0
while n > 0:
	aa = 2 ** n
	chal = 2 ** n
	for i in range(aa, aa + chal, 2):
		ans += abs(lis[i] - lis[i + 1])
		j = max(lis[i], lis[i + 1])
		lis[i // 2] += j
	n -= 1
print(ans)


n = int(input())
V = 2 ** (n + 1) - 1
lights = [0] * (V + 1)
rem_lights = [0] * (V + 1)
for (i, v) in enumerate(input().split()):
	lights[i + 2] = int(v)
stack = [3, 2]
while stack:
	i = stack.pop()
	rem_lights[i] = rem_lights[i // 2] + lights[i]
	if 2 * i < V:
		stack.append(2 * i + 1)
		stack.append(2 * i)
m = max(rem_lights)
for i in range(2 ** n, 2 ** (n + 1) - 1, 2):
	rem_lights[i] = m - rem_lights[i]
	rem_lights[i + 1] = m - rem_lights[i + 1]
while n:
	for i in range(2 ** n, 2 ** (n + 1) - 1, 2):
		small = min(rem_lights[i], rem_lights[i + 1])
		rem_lights[i // 2] = small
		rem_lights[i] -= small
		rem_lights[i + 1] -= small
	n -= 1
print(sum(rem_lights))


__author__ = 'artyom'
n = int(input())
a = [0, 0] + list(map(int, input().split()))
comp = 0
for i in range(2 ** (n + 1) - 1, 1, -2):
	diff = abs(a[i] - a[i - 1])
	comp += diff
	a[i // 2] += max(a[i], a[i - 1])
print(comp)


n = int(input())
A = [0] + list(map(int, input().split()))
C = 0
for i in range(2 ** n - 2, -1, -1):
	C += abs(A[i * 2 + 1] - A[i * 2 + 2])
	A[i] += max(A[i * 2 + 1], A[i * 2 + 2])
print(C)


import fileinput

def parent_id(elem_id):
	return int(elem_id / 2)

def children_ids(elem_id):
	return (elem_id * 2, elem_id * 2 + 1)

def solve(lights):

	def solve_subtree(root_id):
		(a, b) = children_ids(root_id)
		if a >= len(lights):
			return (0, lights[root_id])
		else:
			(needed_a, val_a) = solve_subtree(a)
			(needed_b, val_b) = solve_subtree(b)
			max_val = max(val_b, val_a)
			return (needed_a + needed_b + (2 * max_val - (val_a + val_b)), max_val + lights[root_id])
	(needed, val) = solve_subtree(1)
	return needed

def __starting_point():
	data = list(iter(fileinput.input()))
	lights = [0, 0] + list(map(int, data[1].split()))
	print(solve(lights))
__starting_point()


import math
import sys
import collections

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

def omnompark():
	n = int(input())
	l = list(In())
	ans = 0
	for i in range(len(l) - 1, -1, -1):
		if i % 2:
			if l[i - 1] > l[i]:
				ans += l[i - 1] - l[i]
				l[i] = l[i - 1]
			else:
				ans += l[i] - l[i - 1]
				l[i - 1] = l[i]
			l[i // 2 - 1] += l[i]
	return ans
print(omnompark())


def result(i):
	global ans
	temp = 0
	if i < 1 << n:
		temp = (result(2 * i), result(2 * i + 1))
		ans += abs(temp[0] - temp[1])
		temp = max(temp)
	return lights[i] + temp
n = int(input())
lights = [0, 0] + list(map(int, input().split()))
ans = 0
result(1)
print(ans)


def main():
	(n, l, res) = (2 ** (int(input()) + 1) - 2, [0, 0], 0)
	l.extend(map(int, input().split()))
	while n:
		(a, b) = (l[n], l[n + 1])
		if a < b:
			l[n // 2] += b
			res += b - a
		else:
			l[n // 2] += a
			res += a - b
		n -= 2
	print(res)
main()


n = int(input())
w = [0, 0] + list(map(int, input().split()))
val = [0 for i in range(100500)]
ans = [0 for i in range(100500)]

def dfs(i):
	if i >= 2 ** n:
		ans[i] = 0
		val[i] = 0
	else:
		dfs(2 * i + 1)
		dfs(2 * i)
		ans[i] = ans[2 * i] + ans[2 * i + 1]
		val[i] = max(val[2 * i] + w[2 * i], val[2 * i + 1] + w[2 * i + 1])
		ans[i] += 2 * val[i] - (val[2 * i] + w[2 * i]) - (val[2 * i + 1] + w[2 * i + 1])
dfs(1)
print(ans[1])


n = int(input())
t = 0
tmp = list(map(int, input().split()))
l = 2 ** (n + 1) - 1
d = [0] + [0] * (l - 1)
for i in range(1, l):
	pr = (i - 1) // 2
	d[i] = d[pr] + tmp[i - 1]
b = 2 ** n
c = d[-b:]
m = max(c)
v = [0] * b
for i in range(b):
	v[i] = m - c[i]
for i in range(n):
	pos = 0
	for j in range(0, b, 2):
		k = min(v[j], v[j + 1])
		t += max(v[j], v[j + 1]) - k
		v[pos] = k
		pos += 1
	b //= 2
	v = v[:b]
print(t)


def main():
	n = int(input())
	a = list(map(int, input().split()))
	d = 0
	count = 0
	for j in range(n, 0, -1):
		for i in range(2 ** j - 2, 2 ** (j + 1) - 2, 2):
			d = max(a[i], a[i + 1]) - min(a[i], a[i + 1])
			count += d
			if i:
				a[i // 2 - 1] += max(a[i], a[i + 1])
	print(count)
main()


input()
a = [-1]
a.extend(list(map(int, input().split())))
ans = 0
for i in range(len(a) - 1, 1, -2):
	ans += abs(a[i] - a[i - 1])
	a[i // 2 - 1] += max(a[i], a[i - 1])
print(ans)


n = int(input())
park = input().split(' ')
park = [int(i) for i in park]
park.insert(0, 0)
lights = [0 for i in range(2 ** (n + 1) - 1)]
res = 0
for k in range(n, 0, -1):
	for (i, j) in tuple(enumerate(park))[2 ** k - 1:2 ** (k + 1) - 1:2]:
		res += abs(j + lights[i] - park[i + 1] - lights[i + 1])
		lights[i // 2] = max(j + lights[i], park[i + 1] + lights[i + 1])
print(res)


n = int(input())
alen = 2 ** (n + 1)
a = [0 for i in range(alen)]
inp = input().split()
for i in range(len(inp)):
	a[i + 2] = int(inp[i])
answer = 0
while n > 0:
	index = 2 ** n
	for i in range(index, index * 2, 2):
		left = a[i]
		right = a[i + 1]
		diff = abs(left - right)
		bigone = max(left, right)
		answer += diff
		a[i // 2] += bigone
	n = n - 1
print(answer)


n = int(input())
a = list(map(int, input().split()))
a = [0, 0] + a[:]
l = len(a)

def dfs(node, p):
	if node >= l:
		return 0
	p = a[node]
	q = dfs(2 * node, p)
	r = dfs(2 * node + 1, p)
	p += max(q, r)
	global c
	c = c + abs(q - r)
	return p
c = 0
dfs(1, 0)
print(c)


from itertools import product
n = int(input())
a = list(map(int, input().split()))
k = 1
cnt = []
for i in product([0, 1], repeat=n):
	k = 1
	v = 0
	for j in range(n):
		k = k * 2 + i[j]
		if k - 2 < len(a):
			v += a[k - 2]
	cnt.append(v)
mini = -1
for i in range(len(cnt)):
	if cnt[i] > mini:
		mini = cnt[i]
ans = 0
for i in range(1, n + 1):
	minicur = -1
	k = 0
	k1 = 2 ** (n - i)
	for j in range(2 ** i):
		minicur = -1
		for l in range(k, k1):
			if cnt[l] > minicur:
				minicur = cnt[l]
		for l in range(k, k1):
			cnt[l] += mini - minicur
		ans += mini - minicur
		k += 2 ** (n - i)
		k1 += 2 ** (n - i)
print(ans)