Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Phantasialand boasts of its famous theme park. The park is frequently visited. It is quite large park that some tourists visit it more than once to fully appreciate its offerings. One day, our Chefs decided to visit the park. There are total n Chefs, i-th of them wants to visit the park t_{i} times.

Usually, the entry ticket for the park is very expensive. Today, being a weekend, park had an interesting offer for the visitors, "1x Zahlen, 2x Spaß" (pay once, visit twice), i.e. you can get a second free visit after the first paid visit. The procedure for visiting the park and availing the offer is as follows.
First time visitors should buy a ticket at the entrance of the park. Along with the ticket, you are offered an option of availing a voucher if you want a second visit.
Enter the theme park, enjoy your visit. While returning make sure to sign your name in the voucher. Any unsigned voucher will not allowed to take out of the park.
After the visit is done, the ticket counter takes back your ticket.
If it is your second time visit, then the counter will take back your voucher. No new voucher will be provided to you as you have already availed the offer.
You can avail the offer as many times as you wish in a day, i.e. offer is applicable for each visit with a paid ticket.

Obviously, this procedure has a flaw. The counter doesn't ask you to sign your name on the voucher at the time of providing it to make sure that the person buying the ticket is the one signing the voucher. So, if more than one Chefs enter the park, they can exchange their vouchers while they are inside the park.

Chefs thought of exploiting this flow. They wanted to buy minimum number of tickets. Can you help them in finding how many minimum tickets they should buy?

Let us take an example. There are two Chef's, Alice and Bob. Alice wants to visit the park three times and Bob only once. For their first visits, each of them buys a ticket and obtains their vouchers and visits the park. After they have entered their park, Bob gives his voucher to Alice. Alice signs her name on her own voucher and on the voucher given by Bob. In this way, she has two vouchers, which she can use to visit the park two more times. So, in total by buying two tickets, Alice can visit three times and Bob once.

------ Input ------ 

The first line of the input contains a single integer n denoting the number of Chefs.
The second line contains n space-separated integers t_{1}, t_{2}, ..., t_{n}, where t_{i} denotes the number of times i-th Chef wants to visit the park.

------ Output ------ 

Output a single integer corresponding to the minimum number of tickets Chefs needs to buy.

------ Constraints ------ 

$1 ≤ n ≤ 10^{5}$
$1 ≤ t_{i} ≤ 10^{4}$

----- Sample Input 1 ------ 
2
3 1
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 
Example case 1. This example is already explained in the problem statement.

----- Sample Input 2 ------ 
4
1 2 3 3
----- Sample Output 2 ------ 
5
----- explanation 2 ------

Difficulty: MEDIUM

Starter code:

Solutions:
import math
n = int(input())
sum = 0
for i in input().split():
	sum += int(i)
ans = max(sum // 2, math.ceil(sum / 2))
print(max(ans, n))


t = int(input())
a = list(map(int, input().split()))
s = sum(a)
if s % 2 == 0:
	s = int(s / 2)
else:
	s = int(s / 2) + 1
if t > s:
	print(t)
else:
	print(s)


n = int(input())
a = list(map(int, input().split()))
b = sum(a)
if b % 2 == 0:
	c = b // 2
else:
	c = b // 2 + 1
if c < n:
	print(n)
else:
	print(c)


import math
n = int(input())
v = sum(list(map(int, input().split())))
print(max(n, math.ceil(v / 2)))


n = int(input())
print(max(n, (sum(map(int, input().split(' '))) + 1) // 2))


n = int(input())
t = [int(a) for a in input().split()]
m = sum(t)
if m % 2 == 0:
	res = m // 2
else:
	res = m // 2 + 1
print(max(res, n))


import math
n = int(input())
visits = list(map(int, input().split()))
temp = sum(visits)
res = math.ceil(temp / 2)
res = max(n, res)
print(res)


import math

def soln(n, arr):
	cs = sum(arr)
	if cs / 2 > n:
		return math.ceil(cs / 2)
	return n
n = int(input())
arr = list(map(int, input().split()))
print(soln(n, arr))


n = int(input())
t = list(map(int, input().split()))
m = sum(t)
if m % 2 == 0:
	res = m // 2
else:
	res = m // 2 + 1
if res < n:
	print(n)
else:
	print(res)


import math
n = int(input())
tot = 0
l = list(map(int, input().split(' ')))
tot = sum(l)
voucher = n
rem = tot - n
if rem == 0:
	print(n)
elif rem - voucher > 0:
	print(n + math.ceil((rem - voucher) / 2))
else:
	print(n)


n = int(input())
t = list(map(int, input().split()))
somme = 0
for i in range(n):
	somme += t[i]
tickets = somme - 2 * n
if tickets <= 0:
	print(n)
elif tickets % 2 == 0:
	print(n + tickets // 2)
else:
	print(n + tickets // 2 + 1)


def solution(arr):
	entrance = len(arr) * 2
	diff = sum(arr) - entrance
	cool = len(arr) + diff // 2 + diff % 2
	return max(cool, len(arr))
try:
	t = input()
	for test_case in range(int(t)):
		arr = [int(e) for e in input().split()]
		print(solution(arr))
except EOFError:
	pass


t = int(input())
x = input().split(' ')
x = [int(i) for i in x]
y = (sum(x) + 1) // 2
if y > t:
	print(y)
else:
	print(t)


n = int(input())
k = n
l = list(map(int, input().split()))
n = max(sum(l) - 2 * n, 0)
print(k + n // 2 + n % 2)


from math import ceil
n = int(input())
l = list(map(int, input().split()))
a = ceil(sum(l) / 2)
print(n if a < n else a)


import math
n = int(input())
a = list(map(int, input().split()))
s = 0
for i in a:
	s = s + i
c = n * 2
if s > c:
	d = s - c
	f = math.ceil(d / 2)
	print(f + n)
else:
	print(n)


noChefs = int(input())
chefsChoice = input().split()
sum = 0
for i in chefsChoice:
	sum += int(i)
if sum % 2 != 0:
	sum += 1
print(max(int(sum / 2), noChefs))


n = int(input())
a = sorted([int(x) for x in input().split()])
(ans, i) = (0, 0)
x = 0
while i < n:
	if a[i] < x:
		a[i] = 0
		x -= a[i]
	else:
		a[i] -= x
		x = 0
	ans += a[i] // 2
	if a[i] % 2 != 0:
		ans += 1
		x += 1
	i += 1
print(max([ans, n]))


import math
n = int(input())
sumu = sum(map(int, input().split()))
if sumu <= n * 2:
	print(n)
else:
	k = sumu - n * 2
	ans = math.ceil(k / 2)
	print(n + ans)


import math
N = int(input())
times = [int(n) for n in input().split()]
available = 2 * N
required = 0
for t in times:
	required += t
diff = required - available
if diff > 0:
	to_buy = math.ceil(diff / 2.0)
	print(N + to_buy)
	print('\n')
else:
	print(N)
	print('\n')


n = int(input())
arr = [int(i) for i in input().split()]
print(max(n, (sum(arr) + 1) // 2))


import math
n = int(input())
chefs = list(map(int, input().split()))
s = sum(chefs)
if s > 2 * n:
	n = math.ceil(s / 2)
print(n)


import math
n = int(input())
a = list(map(int, input().split()))
count = 0
count += n
sum = 0
for i in range(n):
	sum += a[i]
sum -= 2 * n
if sum > 0:
	count += math.ceil(sum / 2)
print(count)


import math
n = int(input())
t = list(map(int, input().split()))
summ = sum(t)
ans = math.ceil(summ / 2)
if ans < n:
	print(n)
else:
	print(ans)


from math import *
n = int(input())
x = list(map(int, input().split()))
a = 0
for j in x:
	a += j / 2
b = ceil(a)
if b < n:
	print(n)
else:
	print(b)


n = int(input())
nli = list(map(int, input().split()))
sm = sum(nli)
if 2 * n >= sm:
	print(n)
elif sm % 2 == 0:
	print(sm // 2)
else:
	print((sm + 1) // 2)


import math
n = int(input())
t = [int(x) for x in input().split()]
s = sum(t)
if s <= 2 * n:
	print(n)
else:
	print(math.ceil(s / 2))


n = int(input())
l = list(map(int, input().split()))
t = sum(l)
if t % 2 == 0:
	d = t // 2
elif t % 2 == 1:
	d = t // 2 + 1
if n > d:
	print(n)
else:
	print(d)


import math
n = int(input())
t = [int(i) for i in input().split() if int(i) != 0]
if len(t) == n:
	t_visit = sum(t)
	min_t = max(math.ceil(t_visit / 2), n)
	print(min_t)


import math
n = int(input())
l = list(map(int, input().split()))
p = sum(l)
print(max(n, math.ceil(p / 2)))


n = int(input())
t = [int(i) for i in input().split()]
op = n
rem = still = 0
for i in range(n):
	t[i] -= 2
	if t[i] < 0:
		rem += -1 * t[i]
	elif t[i] > 0:
		still += t[i]
if still > rem:
	still -= rem
	if still % 2 == 0:
		op += still // 2
	else:
		op += still // 2 + 1
print(op)


n = int(input())
l = list(map(int, input().split()))
from math import ceil
visits = max(ceil(sum(l) / 2), n)
print(visits)


import math
m = int(input())
p = [int(i) for i in input().split() if int(i) != 0]
if len(p) == m:
	p_visit = sum(p)
	min_p = max(math.ceil(p_visit / 2), m)
	print(min_p)


import math as m
t = int(input())
x = list(map(int, input().split()))
p = sum(x)
p = p - 2 * t
total = t
if p > 0:
	total += int(m.ceil(p / 2.0))
print(total)


n = int(input())
c = n
t = list(map(int, input().split()))
val = 0
for i in range(n):
	val += t[i]
tot = n
val -= 2 * n
if val > 0:
	tot += val // 2
	if val % 2 > 0:
		tot += 1
print(tot)


n = int(input())
T = [int(i) for i in input().split()]
print(max(n, -(-sum(T) // 2)))


length = int(input())
total = sum(map(int, input().split()))
extra_visits = total - 2 * length
ans = length
if extra_visits > 0:
	ans += extra_visits // 2
	if extra_visits & 1:
		ans += 1
print(ans)


N = int(input())
buy = 0
T = input().split(' ')
for i in range(N):
	buy += int(T[i])
if buy % 2 == 0:
	buy /= 2
else:
	buy /= 2
	buy += 1
print(int(max(buy, N)))


import math
n = int(input())
l = [int(x) for x in input().split()]
t = sum(l)
ticket = n
t = t - n * 2
if t > 0:
	ticket = ticket + math.ceil(t / 2)
print(ticket)


import sys
f = sys.stdin

def solve2(x):
	return max(len(x), (sum(x) + 1) // 2)
t = int(f.readline())
n = [int(x) for x in f.readline().split()]
print(solve2(n))


import math
n = int(input())
l = list(map(int, input().split()))
s = sum(l)
if s > n * 2:
	diff = s - n * 2
	print(n + math.ceil(diff / 2))
else:
	print(n)


n = int(input())
A = list(map(int, input().strip().split()))
s = sum(A)
a = s - 2 * n
ans = n
if a > 0:
	ans = ans + (a + 1) // 2
print(ans)


import math

def solution(arr):
	return max(len(arr), math.ceil(sum(arr) / 2))
try:
	t = input()
	for test_case in range(int(t)):
		arr = [int(e) for e in input().split()]
		print(solution(arr))
except EOFError:
	pass


import math
n = int(input())
t = [int(x) for x in input().split()]
print(max(n, math.ceil(sum(t) / 2)))


n = int(input())
a = [int(i) for i in input().strip().split()]
a.sort()
ev = []
od = []
odon = []
odd = 0
even = 0
tick = 0
one = a.count(1)
v = 0
v += one
tem = 0
for i in a:
	if i % 2 == 0:
		ev.append(i)
	else:
		od.append(i)
		if i != 1:
			odon.append(i)
for i in range(len(odon)):
	if one > 0:
		odon[i] -= 1
		one -= 1
for i in range(len(ev)):
	ev[i] -= 2
	v += 1
for i in range(len(odon)):
	if odon[i] % 2 != 0:
		one += 1
		tem += 1
		odon[i] -= 1
for i in range(len(odon)):
	if odon[i] != 0:
		odon[i] -= 2
		v += 1
te = sum(ev) + sum(odon)
te -= one
if te % 2 == 0:
	te /= 2
else:
	te = (te + 1) / 2
v += max(te, 0)
v += tem
print(int(v))