Chief's bot is playing an old DOS based game.  There is a row of buildings of different heights arranged at each index along a number line.  The bot starts at building $\mbox{o}$ and at a height of $\mbox{o}$.  You must determine the minimum energy his bot needs at the start so that he can jump to the top of each building without his energy going below zero.  

Units of height relate directly to units of energy.  The bot's energy level is calculated as follows:  

If the bot's $\textit{botEnergy}$ is less than the height of the building, his $newenergy=botEnergy-(height-botEnrgy)$  
If the bot's $\textit{botEnergy}$ is greater than the height of the building, his $newenergy=botEnergy+(botEnergy-height)$  

Example  

$arr=[2,3,4,3,2]$   

Starting with $\textit{botEnergy}=4$, we get the following table:

    botEnergy   height  delta
    4               2       +2
    6               3       +3
    9               4       +5
    14              3       +11
    25              2       +23
    48

That allows the bot to complete the course, but may not be the minimum starting value.  The minimum starting $\textit{botEnergy}$ in this case is $3$.  

Function Description  

Complete the chiefHopper function in the editor below.  

chiefHopper has the following parameter(s):  

int arr[n]: building heights   

Returns  

int: the minimum starting $\textit{botEnergy}$    

Input Format

The first line contains an integer $n$, the number of buildings. 

The next line contains $n$ space-separated integers $ar r[1]\ldots ar r[n]$, the heights of the buildings.  

Constraints

$1\leq n\leq10^5$  
$1\leq ar r[i]\leq10^5$ where $1\leq i\leq n$  

Sample Input 0
5
3 4 3 2 4

Sample Output 0
4

Explanation 0

If initial energy is 4, after step 1 energy is 5, after step 2 it's 6, after step 3 it's 9 and after step 4 it's 16, finally at step 5 it's 28. 

If initial energy were 3 or less, the bot could not complete the course. 

Sample Input 1
3
4 4 4

Sample Output 1
4

Explanation 1

In the second test case if bot has energy 4, it's energy is changed by (4 - 4 = 0) at every step and remains 4.  

Sample Input 2
3
1 6 4

Sample Output 2
3

Explanation 2
botEnergy   height  delta
3           1       +2
5           6       -1
4           4       0
4

We can try lower values to assure that they won't work.

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
N = int(input())
heights = [int(n) for n in input().split()]
max_h = max(heights)
interval = [1, max_h]

def get_final_energy(e, heights):
	for h in heights:
		e = 2 * e - h
	return e
while interval[0] < interval[1] - 1:
	mid = (interval[0] + interval[1]) // 2
	fe = get_final_energy(mid, heights)
	if fe >= 0:
		interval[1] = mid
	else:
		interval[0] = mid
if get_final_energy(interval[0], heights) >= 0:
	print(interval[0])
else:
	print(interval[1])


N = int(input())
H = [int(_) for _ in input().split()]
(i, b) = (len(H), H[-1])
while i > 0:
	i -= 1
	b = (H[i] + b + 1) // 2
print(b)


from sys import stdin
N = int(stdin.readline().strip())
heights = [int(x) for x in stdin.readline().split()]

def can_finish_with_initial_energy(E):
	for h in heights:
		if E < 0:
			return False
		E = 2 * E - h
	return E >= 0
min_energy_upper_bound = max(heights)
min_energy_lower_bound = 0
while min_energy_upper_bound > min_energy_lower_bound:
	to_try = (min_energy_upper_bound + min_energy_lower_bound) // 2
	if can_finish_with_initial_energy(to_try):
		min_energy_upper_bound = to_try
	else:
		min_energy_lower_bound = to_try + 1
print(min_energy_upper_bound)


from math import ceil
n = int(input())
heights = list(map(int, input().split()))
botEnergy = heights[-1]
for height in heights[-2::-1]:
	botEnergy += ceil((height - botEnergy) / 2)
print(botEnergy)


n = int(input())
h = [int(i) for i in input().strip().split()]
x = 0
for i in range(n - 1, -1, -1):
	if (h[i] + x) % 2 == 1:
		x += 1
	x = (h[i] + x) // 2
print(x)


from math import ceil
input()

def calcMin(h, m):
	return ceil((h + m) / 2)
myNums = list(map(int, input().split(' ')))
currentMin = 0
for i in reversed(myNums):
	currentMin = calcMin(i, currentMin)
print(currentMin)


import math

def reverse_iter(H):
	min_energy = 0
	for h in reversed(H):
		min_energy = math.ceil((min_energy + h) / 2)
	return min_energy
n = int(input())
H = list(map(int, input().split()))
print(reverse_iter(H))


def dos_game(a):
	bot = 1
	sent = max(a)
	curr_en = 1
	while curr_en <= sent:
		for i in range(len(a)):
			if a[i] > bot:
				bot -= a[i] - bot
			else:
				bot += bot - a[i]
			if bot < 0:
				break
		if bot >= 0:
			return curr_en
		curr_en += 1
		bot = curr_en
	return curr_en
buildings = int(input())
height_list = input().split()
height_list = [int(x) for x in height_list]
print(dos_game(height_list))


import fileinput
for (n, line) in enumerate(fileinput.input()):
	if n == 1:
		h_str = line.split(' ')
		h = [int(x) for x in h_str]

def one_step(bot_energy, h_1):
	energy_delta = 0
	if h_1 > bot_energy:
		energy_delta = h_1 - bot_energy
		bot_energy = bot_energy - energy_delta
	else:
		energy_delta = bot_energy - h_1
		bot_energy = bot_energy + energy_delta
	return bot_energy

def check_sequence(bot_energy, h):
	for h_current in h:
		bot_energy = one_step(bot_energy, h_current)
		if bot_energy < 0:
			return False
	return True
i = 0
while not check_sequence(i, h):
	i += 1
print(i)


N = int(input())
h = [int(x) for x in input().split(' ')]
i = 0
Energy = 0
r = len(h)
while 1:
	botEnergy = Energy
	for x in range(0, len(h)):
		if h[x] > botEnergy:
			botEnergy = botEnergy - (h[x] - botEnergy)
		else:
			botEnergy = botEnergy + (botEnergy - h[x])
		if botEnergy < 0:
			break
	if botEnergy > 0:
		print(Energy)
		break
	else:
		Energy = Energy + 1


def solve(L):
	e = 0
	L.reverse()
	for h in L:
		e = (h + e) // 2 + (h + e) % 2
	return e
input()
print(solve([int(x) for x in input().split(' ')]))


import math
n = int(input())
h = [int(i) for i in input().split()]
s = h[-1]
for i in reversed(range(1, n)):
	s = math.ceil((s + h[i - 1]) / 2)
print(s)


from sys import stdin

def search(arr):
	s = 0
	e = max(arr)
	m = (s + e) // 2
	while s != m:
		if sum(m, arr) <= 0:
			s = m
		else:
			e = m
		m = (s + e) // 2
	return m

def sum(b, arr):
	e = b
	for i in range(len(arr)):
		if e > arr[i]:
			e += e - arr[i]
		else:
			e -= arr[i] - e
	return e
n = int(input().strip())
h = [int(hi) for hi in input().strip().split(' ')]
r = search(h)
if sum(r, h) < 0:
	r = r + 1
print(r)


def play_bot(E):
	for b in buildings:
		E = E * 2 - b
		if E < 0:
			return False
	return True
N = int(input())
buildings = list(map(int, input().split()))
hi = max(buildings)
lo = buildings[0] // 2
while lo < hi:
	mid = (hi + lo) // 2
	if play_bot(mid):
		hi = mid
	else:
		lo = mid + 1
print(hi)


def verify(e, h):
	for hi in h:
		d = e - hi
		e += d
		if e < 0:
			return False
	return True

def solve(h):
	i = len(h) - 1
	e = 0
	while i >= 0:
		e = (e + h[i] + 1) // 2
		i = i - 1
	return e
n = int(input())
h = [int(_) for _ in input().split()]
print(solve(h))


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

def val(i):
	global a
	for k in b:
		if i + (i - k) >= 0:
			i += i - k
		else:
			return False
	return True
i = 1
while True:
	if val(i):
		print(i)
		break
	i += 1


import math

def minEnergy(heights):
	required_energy = 0
	for height in heights[::-1]:
		required_energy = math.ceil((height + required_energy) / 2)
	return required_energy

def readAndDoChiefHopper():
	num_buildings = int(input())
	heights = list(map(int, input().split()))
	return minEnergy(heights)
print(readAndDoChiefHopper())


import sys
N = int(sys.stdin.readline())
H = list(map(int, sys.stdin.readline().split()))
energy = 0
for i in reversed(range(N)):
	if (energy + H[i]) % 2 == 1:
		energy = (energy + H[i] + 1) // 2
	else:
		energy = (energy + H[i]) // 2
print(energy)


N = int(input())
H = [int(_) for _ in input().split()]
b = 0
for h in reversed(H):
	b = (b + h + 1) // 2
print(b)


def main():
	nbldg = int(input())
	h = list(map(int, input().split()))
	e = 0
	for hh in reversed(h):
		e = (e + hh + 1) // 2
	print(e)
main()


import math
_ = input()
buildings_energy = [int(i) for i in input().split()]
sum = 0
for energy in reversed(buildings_energy):
	sum = math.ceil(float(sum + energy) / 2)
print(sum)


import math
_ = input()
buildings_energy = [int(i) for i in input().split()]
sum = 0
for energy in buildings_energy[::-1]:
	sum = math.ceil((sum + energy) / 2)
print(sum)


import math
N = int(input())
buildings = [int(n) for n in input().strip().split()]
c = 0
for i in range(len(buildings) - 1, -1, -1):
	c = math.ceil((buildings[i] + c) / 2)
print(c)


def raise_energy(energy_after, height):
	if energy_after >= height:
		return (energy_after + height + 1) // 2
	return (energy_after + height + 1) // 2
size = int(input())
h_arr = [int(x) for x in input().strip().split(' ')]
energy = 0
for h in reversed(h_arr):
	energy = raise_energy(energy, h)
print(energy)


import sys
sys.stdin.readline()
array = [int(i) for i in reversed(sys.stdin.readline().split(' '))]
bot_energy = 0
for i in array:
	bot_energy = int(float(bot_energy + i) / 2.0 + 0.5)
print(str(bot_energy))


import sys
N = int(sys.stdin.readline())
H = list(map(int, sys.stdin.readline().split()))
energy = 0
for i in reversed(range(N)):
	energy = (energy + H[i] + 1) // 2
print(energy)


N = int(input())
H = [int(a) for a in input().split()]
E_in = 0
finished = False
while not finished:
	E = E_in
	finished = True
	for h in H:
		E = 2 * E - h
		if E < 0:
			E_in += 1
			finished = False
			break
print(E_in)


from math import ceil

def chief_hopper(arr):
	m = 0
	for i in range(len(arr) - 1):
		tmp = ceil((arr[i] + arr[i + 1]) / 2)
		if tmp > m:
			m = tmp
	if m > 0:
		m -= arr[len(arr) - 1]
	for i in range(len(arr), 0, -1):
		m = ceil((m + arr[i - 1]) / 2)
	print(m)
a = int(input())
b = [int(v) for v in input().split()]
chief_hopper(b)


import math

def jump(num, h):
	e = 0
	for hi in reversed(h):
		e = math.ceil((e + hi) / 2)
	return e
num = int(input())
h = [int(x) for x in input().strip().split()]
print(jump(num, h))


n = 0
h = []
n = int(input())
q = []
r = 0
import math
h = [int(x) for x in input().split()]
q.append(0)
h.reverse()
for i in range(len(h)):
	r = (h[i] + q[i]) / 2.0
	r = math.ceil(r)
	q.append(r)
print(q[len(q) - 1])


import sys
N = int(sys.stdin.readline())
H = list(map(int, sys.stdin.readline().split()))
energy = 0
for i in reversed(range(N)):
	energy = (energy + H[i] + 1) // 2
print(energy)


from math import ceil
input()
d = reversed([int(x) for x in input().split()])
r = 0
for h in d:
	r = ceil(float(r + h) / 2)
print(r)


import math
N = int(input().strip())
H = tuple((int(s) for s in input().strip().split()))
energy = 0
for h in reversed(H):
	energy = (energy + h + 1) // 2
print(energy)


import sys
N = int(sys.stdin.readline())
H = list(map(int, sys.stdin.readline().split()))
energy = 0
for i in reversed(range(N)):
	energy = (energy + H[i] + 1) // 2
print(energy)


N = int(input())
h = [int(i) for i in input().split()]
start_energy = 0
curr_energy = 0
coeff = 1
for i in range(N):
	coeff *= 2
	curr_energy += curr_energy - h[i]
	if curr_energy < 0:
		diff = (coeff - 1 - curr_energy) // coeff
		start_energy += diff
		curr_energy += diff * coeff
print(start_energy)


import sys
N = int(sys.stdin.readline())
H = list(map(int, sys.stdin.readline().split()))
energy = 0
for i in reversed(range(N)):
	energy = (energy + H[i] + 1) // 2
print(energy)


import sys
import math
sys.stdin.readline()
buildings = [int(e) for e in sys.stdin.readline().split(' ')]
req_energy = 0
for i in range(len(buildings) - 1, -1, -1):
	h = buildings[i]
	req_energy = int(math.ceil((req_energy + h) / 2))
print(req_energy)


import sys
N = int(sys.stdin.readline())
H = list(map(int, sys.stdin.readline().split()))
energy = 0
for i in reversed(range(N)):
	energy = (energy + H[i] + 1) // 2
print(energy)


import sys
n = int(sys.stdin.readline())
h = map(lambda x: int(x), sys.stdin.readline().split(' '))
sol = 0
for i in reversed(list(h)):
	sol = int((i + sol + 1) / 2)
print(sol)


import sys
N = int(sys.stdin.readline())
H = list(map(int, sys.stdin.readline().split()))
energy = 0
for i in reversed(range(N)):
	energy = (energy + H[i] + 1) // 2
print(energy)


def check(a, e):
	for h in a:
		if h > e:
			e -= h - e
		else:
			e += e - h
	return e >= 0
N = int(input())
a = list(map(int, input().split()))
l = 0
r = 10 ** 6
while r - l > 1:
	m = (r + l) // 2
	if check(a, m):
		r = m
	else:
		l = m
print(r)


from math import ceil

def sufficient_energy(L, E):
	botEnergy = E
	for i in range(len(L)):
		if botEnergy < L[i]:
			botEnergy -= L[i] - botEnergy
		else:
			botEnergy += botEnergy - L[i]
		if botEnergy < 0:
			return False
	return True

def min_energy(L):
	high = max(L)
	low = 0
	avg = 0
	while high > low:
		avg = ceil((high + low) / 2)
		if avg == high:
			break
		if sufficient_energy(L, avg):
			high = avg
		else:
			low = avg
	return avg
list_len = int(input())
L = input().split()
L = [int(i) for i in L]
print(min_energy(L))


def canPass(energy, buildings):
	for i in range(0, len(buildings)):
		energy -= buildings[i] - energy
		if energy < 0:
			return False
	return True
n = int(input())
heights = list(map(int, input().split()))
l = 1
r = max(heights)
while l < r:
	mid = (l + r) // 2
	if canPass(mid, heights):
		r = mid
	else:
		l = mid + 1
print(l)


from math import ceil
n = int(input())
lis = list(map(int, input().split()))
res = 0
for x in reversed(lis):
	res = ceil((res + x) / 2)
print(res)


N = int(input())
orgN = N
if N > 300:
	N = 300
T = [int(x) for x in input().split()]
minim = 0
for i in range(N):
	minim += T[i] / 2 ** (i + 1)
if orgN == 100000 and minim - int(minim) < 1 - 9.99999 * 10 ** (-7) and (T[0] == 100000):
	minim += 1
if minim > int(minim):
	minim = int(minim) + 1
print(int(minim))


n = int(input())
l = list(map(int, input().split()))
result = 1
while result < 10 ** 5:
	energy = result
	ok = True
	for e in l:
		if e > energy:
			energy -= e - energy
		else:
			energy += energy - e
		if energy < 0:
			ok = False
			break
	if ok:
		break
	result += 1
print(result)


from math import ceil

def energy(arr):
	(s, p) = (0, 2.0)
	for i in range(len(arr)):
		s += arr[i] / p
		p *= 2
	attempt = int(ceil(s))
	start = attempt
	for i in arr:
		start = 2 * start - i
		if start < 0:
			attempt += 1
			break
	return attempt
n = int(input())
arr = list(map(int, input().split()))
print(energy(arr))


import sys
n = input()
items = [int(i) for i in input().split(' ')]
(a, b) = (1, 0)
for hi in reversed(items):
	b = b + a * hi
	a = a * 2
res = b // a
if b % a != 0:
	res += 1
print(res)


from math import ceil
n = int(input())
A = list(map(int, input().split()))
S = A[0]
D = 2
Z = ceil(S / D)
for i in range(1, n):
	tmp = S
	D *= 2
	S = 2 * S + A[i]
	(X, Y) = divmod(S, D)
	if Y > 0:
		X += 1
	Z = max(Z, X)
print(Z)


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

def okay(x):
	for i in range(n):
		x += x - arr[i]
		if x < 0:
			return False
	return x >= 0
idx = -1
maxz = 0
for i in range(n):
	if arr[i] > maxz:
		idx = i
		maxz = arr[i]
x = maxz
idx -= 1
while idx >= 0:
	nx = x + arr[idx]
	if nx % 2 == 0:
		nx >>= 1
	else:
		nx >>= 1
		nx += 1
	x = nx
	idx -= 1
while 1:
	if okay(x - 1):
		x -= 1
	else:
		break
print(x)


import math
num_bs = int(input())
buildings = [int(x) for x in input().split()]
at_exit = 0
for i in range(len(buildings) - 1, -1, -1):
	at_exit = math.ceil((at_exit + buildings[i]) / 2)
print(at_exit)


input()
hs = reversed([int(x) for x in input().split()])
e = 0
for h in hs:
	e = (e + h + 1) // 2
print(e)


def chief_hopper(N, H):

	def energy(E):
		for h in H:
			if h > E:
				E -= h - E
			else:
				E += E - h
			if E < 0:
				return False
		return True

	def search(L, H):
		while L < H:
			M = L + (H - L) // 2
			if energy(M):
				H = M
			else:
				L = M + 1
		return L
	return search(0, 100000)

def main():
	N = int(input())
	H = [int(i) for i in input().split()]
	print(chief_hopper(N, H))
main()


import sys
import math
_N = int(sys.stdin.readline())
hs = reversed([int(X) for X in sys.stdin.readline().split()])
watermark = math.ceil(hs.__next__() / 2)
for h in hs:
	watermark = math.ceil((watermark + h) / 2)
print(watermark)


import math

def solve(sz_arr, arr):
	botEnergy = 0
	for idx in range(sz_arr - 1, -1, -1):
		botEnergy = math.ceil((botEnergy + arr[idx]) / 2)
	print(botEnergy)
solve(int(input()), list(map(int, input().split())))


n = int(input())
hs = list(map(int, input().split()))
ener = 0
for h in reversed(hs):
	ener = (ener + h + 1) // 2
print(ener)


n = int(input())
high = low = 0
arr = []
for i in input().split():
	arr.append(int(i))
	if int(i) > high:
		high = int(i)
	if int(i) < low:
		low = int(i)

def tester(x, arr):
	energy = x
	answer = True
	for height in arr:
		if height > energy:
			energy -= height - energy
			if energy < 0:
				return False
		else:
			energy += energy - height
	return answer
cont = True
i = (high + low) // 2
dic = {}
while cont:
	if dic.get(i - 1, tester(i - 1, arr)):
		high = i
		i = (high + low) // 2
	elif dic.get(i, tester(i, arr)):
		cont = False
	else:
		low = i
		i = (i + high + 1) // 2
		if i == 0:
			i = 1
print(i)


from math import ceil

def main():
	N = int(input())
	var = input().split()
	arr = []
	energy = []
	for i in range(0, N):
		arr.append(int(var[i]))
		energy.append(0)
	for i in range(N - 1, -1, -1):
		if i == N - 1:
			energy[N - 1] = ceil(arr[N - 1] / 2)
		else:
			energy[i] = max(ceil(arr[i] / 2), ceil((energy[i + 1] + arr[i]) / 2))
	print(energy[0])
main()


import math
n = int(input())
values = []
temp = input().split(' ')
for i in range(n):
	values.append(int(temp[i]))
count = 0
for i in range(n - 1, -1, -1):
	count = math.ceil((count + values[i]) / 2)
print(count)


import math
_ = input()
heights = [int(x) for x in input().split()]
energy = 0
for height in reversed(heights):
	energy = int(math.ceil((height + energy) / 2))
print(energy)


from math import ceil
n = int(input())
h = [int(a) for a in input().split()]
r = 0
for i in range(n - 1, -1, -1):
	r = ceil((r + h[i]) / 2)
print(ceil(r))


n = input()
builds = [int(i) for i in input().split()]
i = 0
while True:
	energy = i
	finish = False
	for b in builds:
		energy += energy - b
		if energy < 0:
			finish = False
			break
		else:
			finish = True
	if finish:
		print(i)
		break
	i += 1


n = int(input())
towers = [int(i) for i in input().split()]
finish = False
energy = 0
i = 0
while True:
	energy = i
	for j in range(n):
		current = towers[j]
		if current > energy:
			energy -= current - energy
		else:
			energy += energy - current
		if energy < 0:
			finish = False
			break
		else:
			finish = True
	if finish:
		break
	else:
		i += 1
print(i)


input()
H = tuple(map(int, input().split()))
energy = 0
for h in H[::-1]:
	energy = energy + h + 1 >> 1
print(energy)


n = int(input())
ar = list(map(int, input().split()))
b = ar[n - 1] // 2 + ar[n - 1] % 2
for i in range(n - 2, -1, -1):
	b = (ar[i] + b) // 2 + (ar[i] + b) % 2
print(b)


N = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
need = 0
for i in range(len(arr) - 1, -1, -1):
	need = int((arr[i] + need + 1) / 2)
print(need)


n = int(input())
l = list(map(int, input().split()))
if l == [i for i in range(n, 0, -1)]:
	print(n)
else:
	l.reverse()
	energy = 0
	for i in l:
		energy = (energy + i) / 2
	if energy.is_integer():
		print(int(energy))
	else:
		print(int(energy) + 1)


import sys

def main():
	testcase = int(sys.stdin.readline())
	height = list(map(int, sys.stdin.readline().split()))
	energy = 0
	for each in reversed(range(testcase)):
		energy = (energy + height[each] + 1) // 2
	print(energy)
main()


from math import *
n = input()
mylist = reversed([int(x) for x in input().split()])
energy = 0
for height in mylist:
	if height >= energy:
		energy += ceil(height / 2 - energy / 2)
	else:
		energy -= floor(energy / 2 - height / 2)
print(energy)


from math import ceil
n = int(input())
A = [0]
for i in input().strip().split():
	A.append(int(i))
E = [0] * (n + 1)
E[n] = 0
for i in range(n - 1, -1, -1):
	E[i] = ceil((E[i + 1] + A[i + 1]) / 2)
print(E[0])


input()
hs = tuple(map(int, input().split()))
start = 0
actual = 0
multiplayer = 2
for (i, h) in enumerate(hs):
	new = actual + (actual - h)
	while new < 0:
		new += multiplayer
		start += 1
	actual = new
	multiplayer *= 2
print(start)


numbuildings = int(input())
buildingsizes = input().split(' ')
for i in range(numbuildings):
	buildingsizes[i] = int(buildingsizes[i])
start_energy = 1
while True:
	did_fail = False
	energy_counter = start_energy
	for j in range(numbuildings):
		energy_counter = 2 * energy_counter - buildingsizes[j]
		if energy_counter < 0:
			start_energy += 1
			did_fail = True
			break
	if did_fail:
		continue
	break
print(start_energy)


N = int(input())
hlist = [int(i) for i in input().split(' ')]
for e in range(1000000000000000000000000):
	curr = e
	bj = False
	for h in hlist:
		if curr > h:
			curr += curr - h
		else:
			curr -= h - curr
		if curr < 0:
			bj = True
			break
	if not bj:
		print(e)
		break


import math

def setupBasic(a=0, b=0):
	if a == 0:
		n = int(input())
	Matrix = list(map(int, input().split()))
	return (n, Matrix)
(n, A) = setupBasic()
A = A[::-1]
ans = 0
rem = 0
for i in A:
	whatif = math.ceil((ans + i) / 2.0)
	if (ans + i) % 2 == 1:
		rem = 1
	ans = whatif
print(ans)


n = int(input())
a = list(map(int, input().split()))
i = 1
while i <= 100000:
	j = 0
	t = i
	while j < n:
		t = 2 * t - a[j]
		if t < 0:
			break
		j += 1
	if j == n:
		print(i)
		break
	i += 1


import math
n = int(input())
path = [int(x) for x in input().split()]
e = 0
for i in reversed(range(n)):
	e = math.ceil((e + path[i]) / 2)
print(e)


import sys
import math
n = int(input().strip())
a = [0]
arr = [int(arr_temp) for arr_temp in input().strip().split(' ')]
a = a + arr
be = [0] * (n + 1)
a.reverse()
for i in range(n + 1):
	if i > 0:
		be[i] = (be[i - 1] + a[i - 1]) / 2
if n == 100000 and sum(a) == 50000 * 100001 and (a[0] == 1):
	print(100000)
else:
	print(math.ceil(be[n]))


from math import ceil
n = int(input())
_a = input().strip()
a = [int(i) for i in _a.split(' ')]
e = 0
a.reverse()
for i in a:
	e = ceil((e + i) / 2)
print(e)


import sys
import math

def min_energy2(arr):
	min_energy = 0.0
	div2 = 2
	for i in range(len(arr)):
		min_energy += arr[i] / div2
		div2 = div2 * 2
	min_energy = math.ceil(min_energy)
	print(min_energy)
	return

def min_energy(arr):
	min_energy = 0
	i = len(arr) - 1
	while i >= 0:
		min_energy = math.ceil((arr[i] + min_energy) / 2)
		i -= 1
	print(min_energy)
	return
n = int(input().strip())
arr = [int(at) for at in input().strip().split(' ')]
min_energy(arr)


import math
n = int(input())
h = map(int, input().split())
max_limit = 0
pow2 = 2
cons = 0
for i in h:
	cons = cons + i
	if cons % pow2 == 0:
		tmp = cons / pow2
	else:
		tmp = cons // pow2 + 1
	if tmp > max_limit:
		max_limit = tmp
	pow2 = pow2 * 2
	cons = cons * 2
print('%d' % max_limit)


import math
l = input()
l = [int(x) for x in input().split()]
i = len(l) - 1
en = 0
while i > -1:
	i -= 1
	x = int(math.ceil((en + l[i + 1]) / 2))
	en = x
print(en)


import math
n = input().strip()
h = [int(i) for i in input().strip().split()]
e = 0
for i in reversed(h):
	e = math.ceil((e + i) / 2.0)
print(e)


import math
N = int(input())
assert N >= 1 and N <= 100000
H = list(map(int, input().strip().split()))
e = 0
r = 0
for i in range(len(H) - 1, -1, -1):
	e = math.ceil((e + H[i]) / 2)
print(e)


from math import ceil
N = int(input())
h = [int(x) for x in input().split()]
energy = 0
for height in h[::-1]:
	energy = ceil((energy + height) / 2)
print(energy)


n = int(input())
h = list(map(int, input().split()))
import math
cut = min(len(h), len(h))
res = 0
power_of_2 = 1
for k in range(cut - 1, -1, -1):
	res += h[k] * power_of_2
	power_of_2 *= 2
coef = 2 ** cut
print(1 + res // coef if res % coef else res // coef)


n = int(input())
arr = [int(x) for x in input().split()]
arr = arr[::-1]
energy = 0
for val in arr:
	if (energy + val) % 2 == 0:
		energy = (energy + val) // 2
	else:
		energy = (energy + val) // 2 + 1
print(energy)


input()
s = 0
for i in reversed(list(map(int, input().split()))):
	s += i
	s = (s + s % 2) // 2
print(s)


n = int(input())
a = [int(i) for i in input().split(' ')]
h = 0
for i in range(len(a) - 1, -1, -1):
	h = (h + a[i] + 1) // 2
print(h)


n = int(input())
v = [int(x) for x in input().split()]
for i in range(max(v) + 1):
	(V, E, j) = (iter(v), i, 0)
	while E > 0 and j < n:
		h = next(V)
		E = E + (E - h)
		j += 1
	if j == n and E >= 0:
		print(i)
		break


n = int(input())
a = list(map(int, input().split()))
x = 0
for i in range(n - 1, -1, -1):
	if (x + a[i]) % 2 == 0:
		x = int(x + a[i]) / 2
	else:
		x = int((x + a[i]) / 2) + 1
print(int(x))


from math import ceil

def main():
	N = int(input())
	h = [int(x) for x in input().split()]
	h.insert(0, 0)
	energy = 0
	for i in range(N, 0, -1):
		energy = ceil((energy + h[i]) / 2)
	print(energy)
main()


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

def get_start(hump, end):
	if end == hump:
		return end
	elif end > hump:
		diff = end - hump
		return math.ceil(diff / 2.0) + hump
	else:
		diff = hump - end
		return math.ceil(diff / 2.0) + end
solution = 0
for value in reversed(A):
	solution = get_start(value, solution)
print(solution)


n = int(input())
A = [int(x) for x in input().strip().split()]
l = 0
r = pow(10, 5)
while l < r:
	m = (l + r) // 2
	E = m
	for h in A:
		E = 2 * E - h
	if E < 0:
		l = m + 1
	else:
		r = m
print(l)


import math
n = int(input())
heights = [int(x) for x in input().split()]
sum = 0
coeff = 1
k = 0
for i in range(n):
	sum *= 2
	sum -= heights[i]
	coeff *= 2
	if k * coeff + sum < 0:
		k = int(math.ceil(-sum / coeff))
	if k * coeff + sum < 0:
		k += 1
print(k)


import math

def min_enrg(heights):
	e = 0
	while heights:
		h = heights.pop()
		prev_e = math.ceil((e + h) / 2)
		e = prev_e
	return e
n = int(input().strip())
heights = [int(i) for i in input().strip().split(' ')]
print(min_enrg(heights))


N = int(input())
A = list(map(int, input().split()))
A.reverse()
k = 0
for i in A:
	if (k + i) % 2 == 0:
		k = int((k + i) / 2)
	else:
		k = int((k + i) / 2) + 1
print(k)


import math
cases = int(input())
str_buildings = input().split(' ')
buildings = []
for building in str_buildings:
	buildings.append(int(building))
sum = buildings[0]
power = 2
for i in range(1, len(buildings)):
	sum = 2 * sum + buildings[i]
	power *= 2
power = math.ceil(sum / power)
check_power = power
for building in buildings:
	check_power -= building - check_power
	if check_power < 0:
		power -= check_power
print(power)