Monocarp plays "Rage of Empires II: Definitive Edition" — a strategic computer game. Right now he's planning to attack his opponent in the game, but Monocarp's forces cannot enter the opponent's territory since the opponent has built a wall.

The wall consists of $n$ sections, aligned in a row. The $i$-th section initially has durability $a_i$. If durability of some section becomes $0$ or less, this section is considered broken.

To attack the opponent, Monocarp needs to break at least two sections of the wall (any two sections: possibly adjacent, possibly not). To do this, he plans to use an onager — a special siege weapon. The onager can be used to shoot any section of the wall; the shot deals $2$ damage to the target section and $1$ damage to adjacent sections. In other words, if the onager shoots at the section $x$, then the durability of the section $x$ decreases by $2$, and the durability of the sections $x - 1$ and $x + 1$ (if they exist) decreases by $1$ each.

Monocarp can shoot at any sections any number of times, he can even shoot at broken sections.

Monocarp wants to calculate the minimum number of onager shots needed to break at least two sections. Help him!


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of sections.

The second line contains the sequence of integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$), where $a_i$ is the initial durability of the $i$-th section.


-----Output-----

Print one integer — the minimum number of onager shots needed to break at least two sections of the wall.


-----Examples-----

Input
5
20 10 30 10 20
Output
10
Input
3
1 8 1
Output
1
Input
6
7 6 6 8 5 8
Output
4
Input
6
14 3 8 10 15 4
Output
4
Input
4
1 100 100 1
Output
2
Input
3
40 10 10
Output
7


-----Note-----

In the first example, it is possible to break the $2$-nd and the $4$-th section in $10$ shots, for example, by shooting the third section $10$ times. After that, the durabilities become $[20, 0, 10, 0, 20]$. Another way of doing it is firing $5$ shots at the $2$-nd section, and another $5$ shots at the $4$-th section. After that, the durabilities become $[15, 0, 20, 0, 15]$.

In the second example, it is enough to shoot the $2$-nd section once. Then the $1$-st and the $3$-rd section will be broken.

In the third example, it is enough to shoot the $2$-nd section twice (then the durabilities become $[5, 2, 4, 8, 5, 8]$), and then shoot the $3$-rd section twice (then the durabilities become $[5, 0, 0, 6, 5, 8]$). So, four shots are enough to break the $2$-nd and the $3$-rd section.

Source: codeforces | Difficulty: HARD
Tags: Constructive algorithms

Sorting

Greedy algorithms

Complete search

Mathematics


Solutions:
import math
from typing import Tuple, TypeVar
INF = float('inf')
IntOrFloat = TypeVar('IntOrFloat', int, float)

def ceil(value: IntOrFloat) -> IntOrFloat:
	if value == INF:
		return INF
	return math.ceil(value)

def break_adjacent_sections(health: Tuple[int]) -> int:
	minimum = INF
	for i in range(n - 1):
		x = max(health[i], health[i + 1])
		y = min(health[i], health[i + 1])
		if 2 * y <= x:
			value = ceil(x / 2)
		else:
			value = ceil((x + y) / 3)
		if value < minimum:
			minimum = value
	return minimum

def break_alternate_sections(health: Tuple[int]) -> int:
	minimum = INF
	for i in range(n - 2):
		value = health[i] + health[i + 2]
		if value < minimum:
			minimum = value
	result = ceil(minimum / 2)
	return result

def break_unrelated_sections(health: Tuple[int]) -> int:
	health = sorted(health)
	result = ceil(health[0] / 2) + ceil(health[1] / 2)
	return result
n = int(input())
health = tuple(map(int, input().split()))
print(min(break_adjacent_sections(health), break_alternate_sections(health), break_unrelated_sections(health)))


def main():
	n = int(input())
	a = list(map(int, input().split()))
	ans = [0] * (n - 1)
	ans_ = [0] * (n - 2)
	for i in range(n - 1):
		(x1, x2) = (a[i], a[i + 1])
		s = x1 + x2
		min_ = (s + 2) // 3
		(x1, x2) = (max(x1, x2), min(x1, x2))
		if x2 * 2 >= x1:
			ans[i] = min_
		else:
			ans[i] = (x1 + 1) // 2
	for i in range(n - 2):
		(x1, x2) = (a[i], a[i + 2])
		(x1, x2) = (max(x1, x2), min(x1, x2))
		delta = x1 - x2
		ans_[i] = x2 + (delta + 1) // 2
	(min_1, min_2) = (10 ** 9, 10 ** 9)
	for i in a:
		if i < min_1:
			min_2 = min_1
			min_1 = i
		elif i < min_2:
			min_2 = i
	answer = (min_1 + 1) // 2 + (min_2 + 1) // 2
	for i in ans:
		if i < answer:
			answer = i
	for i in ans_:
		if i < answer:
			answer = i
	print(answer)
main()


from collections import Counter, deque
import math
from random import randint
from bisect import bisect
import sys
import re
MOD = 10 ** 9 + 7
MAX = sys.maxsize
MIN = -sys.maxsize

class get:

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

	def str():
		return input().split()

	def float():
		return list(map(float, input().split()))

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

def sqrt(x):
	return int(math.sqrt(x)) + 1

def gcd(*args):
	result = args[0]
	for item in args:
		result = math.gcd(result, item)
	return result

def LCM(a, b):
	return a * b // math.gcd(a, b)

def isPrime(n):
	if n == 1:
		return False
	for i in range(2, sqrt(n)):
		if n % i == 0:
			return False
	return True

def solve():
	n = int(input())
	arr = get.int()
	ans = MAX
	for i in range(0, n - 2):
		ans = min(ans, (arr[i] + arr[i + 2] + 1) // 2)
	for i in range(n - 1):
		(a, b) = (min(arr[i], arr[i + 1]), max(arr[i], arr[i + 1]))
		if a <= b / 2:
			ans = min(ans, (b + 1) // 2)
		else:
			ans = min(ans, math.ceil((a + b) / 3))
	arr.sort()
	ans = min(ans, (arr[0] + 1) // 2 + (arr[1] + 1) // 2)
	print(ans)
solve()


def solve():
	n = int(input())
	l = list(map(int, input().split()))
	mn_ans = l[0] + l[1]
	for i in range(1, n - 1):
		(x, y) = (l[i - 1], l[i + 1])
		if x < y:
			t = x
			x = y
			y = t
		mn_ans = min(mn_ans, y + (x - y + 1) // 2)
	for i in range(0, n - 1):
		curr = 0
		(x, y) = (l[i], l[i + 1])
		if x < y:
			t = x
			x = y
			y = t
		cnt = min(x - y, (x + 1) // 2)
		curr += cnt
		x -= 2 * cnt
		y -= cnt
		if x > 0 and y > 0:
			curr += (x + y + 2) // 3
		mn_ans = min(mn_ans, curr)
	l.sort()
	mn_ans = min(mn_ans, (l[0] + 1) // 2 + (l[1] + 1) // 2)
	print(mn_ans)
t = 1
while t > 0:
	solve()
	t -= 1


n = int(input())
A = list(map(int, input().split()))
S = sorted(A)
ANS = (S[0] + 1) // 2 + (S[1] + 1) // 2
for i in range(n - 2):
	a = A[i]
	b = A[i + 2]
	if a % 2 == 1 and b % 2 == 1:
		ANS = min(ANS, a // 2 + b // 2 + 1)
for i in range(n - 1):
	a = A[i]
	b = A[i + 1]
	if a > b:
		(a, b) = (b, a)
	if b >= 2 * a:
		ANS = min(ANS, (b + 1) // 2)
	else:
		k = b - a
		a -= k
		b -= 2 * k
		rest = a % 3
		ANS = min(ANS, k + a // 3 * 2 + rest)
print(ANS)


def resi():
	n = int(input())
	a = list(map(int, input().split()))
	(min1, min2) = (10000001, 10000001)
	for i in range(n):
		if a[i] <= min1:
			min2 = min1
			min1 = a[i]
		elif a[i] <= min2:
			min2 = a[i]
	res1 = (min1 + 1) // 2 + (min2 + 1) // 2
	res2 = 10000001
	for i in range(n - 1):
		x = min(a[i], a[i + 1])
		y = max(a[i], a[i + 1])
		if y >= 2 * x:
			if res2 > (y + 1) // 2:
				res2 = (y + 1) // 2
		elif res2 > y - x + (2 * (2 * x - y) + 2) // 3:
			res2 = y - x + (2 * (2 * x - y) + 2) // 3
	res3 = 10000001
	for i in range(1, n - 1):
		if res3 > min(a[i - 1], a[i + 1]) + (max(a[i - 1], a[i + 1]) - min(a[i - 1], a[i + 1]) + 1) // 2:
			res3 = min(a[i - 1], a[i + 1]) + (max(a[i - 1], a[i + 1]) - min(a[i - 1], a[i + 1]) + 1) // 2
	print(min(res1, res2, res3))
resi()


import sys
from math import ceil
input = sys.stdin.readline
for _ in range(1):
	n = int(input())
	arr = [int(x) for x in input().split()]
	brr = sorted(arr)
	cand1 = ceil(brr[0] / 2) + ceil(brr[1] / 2)
	cand2 = 1000000000000
	for i in range(n - 1):
		(a, b) = (arr[i], arr[i + 1])
		cand2 = min(cand2, max(ceil((a + b) / 3), ceil(max(a, b) / 2)))
	cand3 = 1000000000000
	for i in range(n - 2):
		(a, b) = (arr[i], arr[i + 2])
		cand3 = min(cand3, a + ceil((b - a) / 2))
	print(min(cand1, cand2, cand3))


from math import ceil
n = int(input())
arr = list(map(int, input().split()))
wyn = 10 ** 12
for x in range(1, n - 1):
	if arr[x - 1] % 2 == 1 and arr[x + 1] % 2 == 1:
		m = min(arr[x - 1], arr[x + 1])
		tmp_wyn = m + (max(arr[x - 1], arr[x + 1]) - m) // 2
	else:
		tmp_wyn = max(arr[x - 1], arr[x + 1])
	if tmp_wyn < wyn:
		wyn = tmp_wyn
for x in range(0, n - 1):
	m1 = max(arr[x], arr[x + 1])
	m2 = min(arr[x], arr[x + 1])
	mc = ceil(m1 / 2)
	if m2 <= mc:
		if mc < wyn:
			wyn = mc
	elif ceil((arr[x] + arr[x + 1]) / 3) < wyn:
		wyn = ceil((arr[x] + arr[x + 1]) / 3)
mina = 10 ** 9
minb = 10 ** 9
for x in arr:
	if x <= mina:
		minb = mina
		mina = x
	elif x < minb:
		minb = x
if ceil(mina / 2) + ceil(minb / 2) < wyn:
	wyn = ceil(mina / 2) + ceil(minb / 2)
print(wyn)


from math import ceil
n = int(input())
l = list(map(int, input().split()))
ans = float('inf')
(f, s) = (float('inf'), float('inf'))
for num in l:
	if num < f:
		s = f
		f = num
	elif num < s:
		s = num
ans = min(ceil(f / 2) + ceil(s / 2), ans)
for i in range(n - 2):
	ans = min(ans, ceil((l[i] + l[i + 2]) / 2))
for i in range(n - 1):
	x = max(l[i], l[i + 1])
	y = min(l[i], l[i + 1])
	if 2 * y <= x:
		ans = min(ans, ceil(x / 2))
	else:
		ans = min(ans, x - y + ceil((4 * y - 2 * x) / 3))
print(ans)


import math
n = int(input())
s = list((int(i) for i in input().split()))
min1 = 10000000
for i in range(n - 1):
	(a, b) = (s[i], s[i + 1]) if s[i] < s[i + 1] else (s[i + 1], s[i])
	if b > a * 2:
		min1 = min(min1, math.ceil(b / 2))
	else:
		min1 = min(min1, math.ceil((a + b) / 3))
for i in range(n - 2):
	(a, b) = (s[i], s[i + 2]) if s[i] < s[i + 2] else (s[i + 2], s[i])
	min1 = min(min1, math.ceil(a // 2 + b // 2 + (0 if a % 2 == 0 and b % 2 == 0 else 1)))
min2 = math.ceil(min(s) / 2)
s.remove(min(s))
min3 = math.ceil(min(s) / 2)
min1 = min(min1, min2 + min3)
print(min1)


n = int(input())
a = list(map(int, input().split()))
ans1 = 10000000
for i in range(n - 1):
	if max(a[i], a[i + 1]) >= 2 * min(a[i], a[i + 1]):
		curr = max(a[i] + 1, a[i + 1] + 1) // 2
	else:
		curr = (a[i] + a[i + 1] + 2) // 3
	if curr < ans1:
		ans1 = curr
ans2 = 10000000
for i in range(1, n - 1):
	x = min(a[i - 1], a[i + 1])
	y = max(a[i - 1], a[i + 1])
	curr = x + (y - x + 1) // 2
	if curr < ans2:
		ans2 = curr
a.sort()
ans3 = (a[0] + 1) // 2 + (a[1] + 1) // 2
print(min(ans1, ans2, ans3))


from math import ceil
n = int(input())
(*a,) = map(int, input().split())
s = sorted(a)
answer = ceil(s[0] / 2) + ceil(s[1] / 2)
for i in range(n - 2):
	x = a[i]
	y = a[i + 2]
	if x > y:
		(x, y) = (y, x)
	res = x
	res += ceil((y - x) / 2)
	answer = min(answer, res)
for i in range(n - 1):
	x = a[i]
	y = a[i + 1]
	if x > y:
		(x, y) = (y, x)
	if y >= x * 2:
		answer = min(answer, ceil(y / 2))
	else:
		res = y - x
		x -= res
		y -= 2 * res
		z = x % 3
		answer = min(answer, res + z + x // 3 * 2)
print(answer)


INT_MAX = 9999999999
n = int(input())
arr = list(map(int, input().split()))
val1 = INT_MAX
val2 = INT_MAX
for i in range(1, n):
	if i < n - 1:
		x = arr[i - 1] + arr[i + 1]
		if x % 2:
			x += 1
		val2 = min(val2, x // 2)
	x = max(arr[i], arr[i - 1])
	y = min(arr[i], arr[i - 1])
	if 2 * y < x:
		if x % 2:
			x += 1
		val2 = min(val2, x // 2)
	else:
		a = x - y
		b = 2 * y - x
		if 2 * b % 3:
			a += 1
		a += 2 * b // 3
		val2 = min(a, val2)
f_val = min(val1, val2)
f2 = min(arr)
arr.remove(min(arr))
f1 = min(arr)
f = f2 // 2
if f2 % 2:
	f += 1
f += f1 // 2
if f1 % 2:
	f += 1
print(min(f, f_val))


from math import ceil
n = int(input())
a = [int(i) for i in input().split()]
b = sorted(a)
ans = ceil(b[0] / 2) + ceil(b[1] / 2)
for i in range(n - 1):
	(target1, target2) = sorted(a[i:i + 2])
	if target2 >= target1 * 2:
		shot = ceil(target2 / 2)
	else:
		dif = target2 - target1
		target1 -= dif
		target2 -= dif * 2
		shot = dif + ceil((target1 + target2) / 3)
	ans = min(ans, shot)
for i in range(n - 2):
	(target1, target2) = (a[i], a[i + 2])
	shot = ceil((target1 + target2) / 2)
	ans = min(ans, shot)
print(ans)


import math
n = int(input())
lst = [10 ** 6 + 1] + list(map(int, input().split())) + [10 ** 6 + 1]
r = 10 ** 9
min1 = 10 ** 9
min2 = 10 ** 9
for i in range(1, n + 1):
	mn = min(lst[i - 1], lst[i + 1])
	mx = max(lst[i - 1], lst[i + 1])
	k = math.ceil((mx - mn) / 2) + mn
	if k < r:
		r = k
	mx = max(lst[i], lst[i + 1])
	mn = min(lst[i], lst[i + 1])
	if mx >= mn * 2:
		k = math.ceil(mx / 2)
		if k < r:
			r = k
	else:
		k = mx - mn
		mn -= k
		k += math.ceil(mn * 2 / 3)
		if k < r:
			r = k
	if min1 >= min2 and lst[i] < min1:
		min1 = lst[i]
	elif min2 >= min1 and lst[i] < min2:
		min2 = lst[i]
k = math.ceil(min1 / 2) + math.ceil(min2 / 2)
if k < r:
	r = k
print(r)


n = int(input())
li = [int(i) for i in input().split()]
ans = 10000000000
for i in range(n - 1):
	cur = 0
	x = li[i]
	y = li[i + 1]
	if x < y:
		x = li[i + 1]
		y = li[i]
	cnt = min(x - y, (x + 1) // 2)
	cur += cnt
	x -= 2 * cnt
	y -= cnt
	if x > 0 and y > 0:
		cur += (x + y + 2) // 3
	ans = min(ans, cur)
for i in range(n - 2):
	x = li[i]
	y = li[i + 2]
	if x < y:
		x = li[i + 2]
		y = li[i]
	cnt = (x - y + 1) // 2
	ans = min(ans, cnt + y)
li.sort()
ans = min(ans, (li[0] + 1) // 2 + (li[1] + 1) // 2)
print(ans)


import math
n = int(input())
q = list(map(int, input().split()))
summ = 9876543212345678987654321
for i in range(n - 1):
	a = min(q[i], q[i + 1])
	b = max(q[i], q[i + 1])
	if b > 2 * a:
		summ = min(summ, math.ceil(b / 2))
	else:
		summ = min(summ, math.ceil((a + b) / 3))
for i in range(n - 2):
	a = min(q[i], q[i + 2])
	b = max(q[i], q[i + 2])
	x = a
	x = x + math.ceil((b - a) / 2)
	summ = min(summ, x)
q.sort()
summ = min(summ, math.ceil(q[0] / 2) + math.ceil(q[1] / 2))
print(summ)


import math
kvs = int(input())
q = list(map(int, input().split()))
s = 9876543212345678987654321
for i in range(kvs - 1):
	anil = min(q[i], q[i + 1])
	barre = max(q[i], q[i + 1])
	if barre > 2 * anil:
		s = min(s, math.ceil(barre / 2))
	else:
		s = min(s, math.ceil((anil + barre) / 3))
for i in range(kvs - 2):
	anil = min(q[i], q[i + 2])
	barre = max(q[i], q[i + 2])
	x = anil
	x = x + math.ceil((barre - anil) / 2)
	s = min(s, x)
q.sort()
s = min(s, math.ceil(q[0] / 2) + math.ceil(q[1] / 2))
print(s)


import sys
input = sys.stdin.readline
n = int(input())
data = list(map(int, input().split()))
temp = sorted(data)
(a, b) = (temp[0], temp[1])
answer = (a + 1) // 2 + (b + 1) // 2
for i in range(1, n):
	t1 = int(1000000000.0)
	if i + 1 < n:
		t1 = data[i - 1] // 2 + data[i + 1] // 2
		t1 += data[i - 1] % 2 | data[i + 1] % 2
	A = max(data[i - 1], data[i])
	B = min(data[i - 1], data[i])
	t3 = t2 = int(1000000000.0)
	if (A + 1) // 2 >= B:
		t2 = (A + 1) // 2
	else:
		t3 = (A + B + 2) // 3
	answer = min(answer, t1, t2, t3)
print(answer)


n = int(input())
arr = list(map(int, input().split()))
mini = max(arr)
for i in range(n):
	if i != n - 1:
		if arr[i] >= arr[i + 1] and arr[i] <= 2 * arr[i + 1] or (arr[i] <= arr[i + 1] and 2 * arr[i] >= arr[i + 1]):
			ans = (arr[i] + arr[i + 1]) // 3
			if (arr[i] + arr[i + 1]) % 3:
				ans += 1
		else:
			ans = max(arr[i], arr[i + 1]) // 2
			if max(arr[i], arr[i + 1]) % 2:
				ans += 1
		if ans < mini:
			mini = ans
		if len(arr) >= 3 and i != 0:
			p1 = max(arr[i - 1], arr[i + 1]) - min(arr[i - 1], arr[i + 1])
			p2 = min(arr[i - 1], arr[i + 1])
			p2 += p1 // 2
			if p1 % 2:
				p2 += 1
			if p2 < mini:
				mini = p2
min1 = min(arr[:2])
min2 = max(arr[:2])
for i in range(2, n):
	if arr[i] <= min1:
		min2 = min1
		min1 = arr[i]
	elif arr[i] <= min2:
		min2 = arr[i]
ans = min1 // 2
if min1 % 2:
	ans += 1
ans += min2 // 2
if min2 % 2:
	ans += 1
if ans < mini:
	mini = ans
print(mini)


n = int(input())
a = list(map(int, input().split()))
b = a[:]
b.sort()
ans = (b[0] + 1) // 2 + (b[1] + 1) // 2
for i in range(n - 1):
	q = max(a[i], a[i + 1])
	w = min(a[i], a[i + 1])
	if q > 2 * w:
		ans = min(ans, (q + 1) // 2)
	else:
		ans = min(ans, (q + w + 2) // 3)
a = [99999999] + a + [99999999]
for i in range(1, n + 1):
	temp = a[i - 1:i + 2]
	att = min(temp[0], temp[2], (temp[1] + 1) // 2)
	temp[0] -= att
	temp[1] -= att * 2
	temp[2] -= att
	temp.sort()
	ans = min(att + (temp[1] + 1) // 2, ans)
print(ans)


import sys
input = sys.stdin.readline

def solve():
	N = int(input())
	INF = 10 ** 20
	a = [INF] + list(map(int, input().split()))
	a.append(INF)
	best = INF
	N = len(a)
	for i in range(1, N - 1):
		best = min(best, max(a[i - 1], a[i + 1]))
		best = min(best, max(min(a[i - 1], a[i + 1]), (a[i] + 1) // 2))
		x = a[i - 1]
		y = a[i + 1]
		if x > y:
			(x, y) = (y, x)
		shots = x + (y - x + 1) // 2
		y -= x
		best = min(shots, best)
	for i in range(N - 1):
		(x, y) = (a[i], a[i + 1])
		if x > y:
			(x, y) = (y, x)
		delta = y - x
		shots = min(delta, x)
		y -= 2 * shots
		x -= shots
		if y == x:
			shots += (y + x + 2) // 3
			best = min(shots, best)
		else:
			assert x == 0
			shots += (y + 1) // 2
			best = min(shots, best)
	a.sort()
	best = min(best, (a[0] + 1) // 2 + (a[1] + 1) // 2)
	print(best)
solve()


(N, A) = (int(input()), list(map(int, input().split())))
c = 1000000
for i in range(N - 2):
	prev = c
	c = min(c, max(A[i], A[i + 2]))
	if A[i] % 2 == A[i + 2] % 2 == 1:
		c = min(c, A[i] // 2 + A[i + 2] // 2 + 1)
for i in range(N - 1):
	x = min(A[i], A[i + 1])
	y = A[i] + A[i + 1] - x
	if min(A[i], A[i + 1]) <= (max(A[i], A[i + 1]) + 1) // 2:
		c = min(c, (max(A[i], A[i + 1]) + 1) // 2)
	else:
		c = min(c, (A[i] + A[i + 1] + 2) // 3)
X = sorted(A)
c = min(c, (X[0] + 1) // 2 + (X[1] + 1) // 2)
print(c)


n = int(input())
l = [int(i) for i in input().split(' ')]
(a, b) = (1000000.0 + 1, 1000000.0 + 1)
for i in l:
	if i < a:
		(a, b) = (i, a)
	elif i < b:
		(a, b) = (a, i)
best = -1
for i in range(n):
	x = l[i]
	tmp = []
	if i > 0:
		tmp.append(l[i - 1])
	if i < len(l) - 1:
		tmp.append(l[i + 1])
	y = min(tmp)
	if x > y:
		(x, y) = (y, x)
	if y >= 2 * x:
		cur = (y + 1) // 2
	else:
		cur = (x + y + 2) // 3
	if len(tmp) == 2:
		cur = min(cur, min(tmp) + (max(tmp) - min(tmp) + 1) // 2)
	x = l[i]
	y = a
	if l[i] == a:
		y = b
	cur = min(cur, (x + 1) // 2 + (y + 1) // 2)
	if cur < best or best < 0:
		best = cur
print(best)


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = list(map(int, inp().split()))
	ans = int(20000000.0)
	for i in range(2, n):
		b = a[i - 2]
		c = a[i]
		(b, c) = (min(b, c), max(b, c))
		ans = min(ans, b + (c - b + 1) // 2)
	for i in range(1, n):
		b = a[i - 1]
		c = a[i]
		(b, c) = (min(b, c), max(b, c))
		z = (b + c + 2) // 3
		y = max(c - z, 0)
		ans = min(ans, y + max(c - y * 2, (b - y + 1) // 2, 0))
		ans = min(ans, (c + 1) // 2 + max(b - (c + 1) // 2 + 1, 0) // 2)
	a.sort()
	ans = min(ans, (a[0] + 1) // 2 + (a[1] + 1) // 2)
	print(ans)

def main():
	solve()
main()


import math
n = int(input())
a = list(map(int, input().split()))
ans = 1000000000
min_nb = 1000000000
for i in range(1, len(a)):
	if i == 1:
		ans = min(ans, max(math.ceil(a[i - 1] / 2), math.ceil((a[i - 1] + a[i]) / 3), math.ceil(a[i] / 2)))
		min_nb = min(min_nb, a[i - 1])
	else:
		ans = min(ans, max(math.ceil(a[i - 1] / 2), math.ceil((a[i - 1] + a[i]) / 3), math.ceil(a[i] / 2)))
		ans = min(ans, max(a[i - 2], a[i]), min(a[i - 2], a[i]) + math.ceil(abs(a[i - 2] - a[i]) / 2))
		ans = min(ans, math.ceil(min_nb / 2) + math.ceil(a[i] / 2))
		min_nb = min(min_nb, a[i - 1])
print(ans)


n = int(input())
a = list(map(int, input().split()))
ind = 0
for i in range(1, n):
	if a[i] < a[ind]:
		ind = i
ind2 = -1
for i in range(n):
	if i == ind:
		continue
	if ind2 == -1:
		ind2 = i
	elif a[i] < a[ind2]:
		ind2 = i

def f(x):
	return (x + 1) // 2
ans = f(a[ind]) + f(a[ind2])
for i in range(1, n - 1):
	ans = min(ans, 1 + f(a[i - 1] - 1) + f(a[i + 1] - 1))
for i in range(1, n):
	x = a[i - 1]
	y = a[i]
	if x > y:
		(x, y) = (y, x)
	cur = 0
	op = min(x, y - x)
	cur += op
	x -= op
	y -= 2 * op
	op = min(x // 3, y // 3)
	x -= 3 * op
	y -= 3 * op
	cur += 2 * op
	if x:
		cur += 1
		y -= 2
		x -= 1
	cur += f(x) + f(y)
	ans = min(ans, cur)
print(ans)


import sys
from math import ceil
input = sys.stdin.readline
for Pythonic__Python in range(1):
	n = int(input())
	l = list(map(int, input().split()))
	ll = []
	ans = int(20000000.0)
	for i in range(n):
		ll.append([l[i], i])
	for j in range(1, n):
		(x, y) = (min(ll[j - 1][0], ll[j][0]), max(ll[j - 1][0], ll[j][0]))
		if y > 2 * x:
			x = int((y + 1) / 2)
		else:
			x = int((x + y + 2) / 3)
		ans = min(ans, x)
	for j in range(2, n):
		(x, y) = (min(ll[j - 2][0], ll[j][0]), max(ll[j - 2][0], ll[j][0]))
		ans = min(ans, int(x + (y - x + 1) / 2))
	ll.sort()
	(x, y) = (ll[0][0], ll[1][0])
	ans = min(ans, int((x + 1) / 2) + int((y + 1) / 2))
	print(ans)


def ff(a, b):
	mx = max(a, b)
	mi = min(a, b)
	ans = 0
	if mi < mx // 2:
		ans = mx // 2 + mx % 2
	else:
		a = (2 * mx - mi) // 3
		ans = a
		mx -= 2 * a
		mi -= a
		if mi > 0:
			ans += mi // 2 + mi % 2
			mx -= mi // 2 + mi % 2
		if mx > 0:
			ans += mx // 2 + mx % 2
	return ans

def f(a, b, c):
	ans1 = min(a, c)
	mi = max(a, c) - min(a, c)
	ans1 += mi // 2 + mi % 2
	ans2 = ff(a, b)
	ans3 = ff(b, c)
	ans = min(ans1, ans2, ans3)
	return ans
n = int(input())
arr = list(map(int, input().split()))
ans = max(arr)
for i in range(1, n - 1):
	tm = f(arr[i - 1], arr[i], arr[i + 1])
	ans = min(tm, ans)
arr.sort()
tm = arr[0] // 2 + arr[0] % 2 + arr[1] // 2 + arr[1] % 2
ans = min(tm, ans)
if len(arr) == 2:
	ans = min(ans, ff(arr[0], arr[1]))
print(ans)


import math
from collections import defaultdict
n = int(input())
lis = list(map(int, input().split()))
vayu = lis.copy()
vayu.sort()

def act(a, b):
	lis = [a, b]
	lis.sort()
	if lis[1] >= lis[0] * 2:
		return math.ceil(lis[1] / 2)
	elif (lis[0] - (lis[1] - lis[0])) % 3 == 0:
		return lis[1] - lis[0] + 2 * ((lis[0] - (lis[1] - lis[0])) // 3)
	else:
		return lis[1] - lis[0] + 2 * ((lis[0] - (lis[1] - lis[0])) // 3) + (lis[0] - (lis[1] - lis[0])) % 3
ans = math.ceil(vayu[0] / 2) + math.ceil(vayu[1] / 2)
for j in range(0, n - 1):
	new = math.ceil(lis[j] / 2)
	if j == 0:
		ans = min(ans, act(lis[j], lis[j + 1]))
	elif j == n - 1:
		ans = min(ans, act(lis[j], lis[j - 1]))
	else:
		ans = min(ans, act(lis[j], lis[j + 1]), act(lis[j], lis[j - 1]))
for j in range(0, n - 2):
	tot = math.ceil((max(lis[j], lis[j + 2]) - min(lis[j], lis[j + 2])) / 2)
	ans = min(ans, min(lis[j], lis[j + 2]) + tot)
print(ans)