You are given a Young diagram. 

Given diagram is a histogram with n columns of lengths a_1, a_2, …, a_n (a_1 ≥ a_2 ≥ … ≥ a_n ≥ 1).

<image> Young diagram for a=[3,2,2,2,1].

Your goal is to find the largest number of non-overlapping dominos that you can draw inside of this histogram, a domino is a 1 × 2 or 2 × 1 rectangle.

Input

The first line of input contain one integer n (1 ≤ n ≤ 300 000): the number of columns in the given histogram.

The next line of input contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 300 000, a_i ≥ a_{i+1}): the lengths of columns.

Output

Output one integer: the largest number of non-overlapping dominos that you can draw inside of the given Young diagram.

Example

Input


5
3 2 2 2 1


Output


4

Note

Some of the possible solutions for the example:

<image> <image>
# n, m = map(int, input().split())
# a = list(map(int, input().split()))
# b = list(map(int, input().split()))
# d_a = {}
# for i in a:
#     if (i%m) not in d_a.keys():
#         d_a[i % m] = 1
#     else:
#         d_a[i % m] += 1
# d_b = {}
# for i in b:
#     if (i%m) not in d_b.keys():
#         d_b[i % m] = 1
#     else:
#         d_b[i % m] += 1
# res_a = list(d_a.items())
# res_b = list(d_b.items())
# res_a = sorted(res_a, key=lambda tup: tup[1], reverse=True)
# res_b = sorted(res_b, key=lambda tup: tup[1], reverse=True)
# print(abs(res_a[0][0] - res_b[0][0]))

#
# n, k = map(int, input().split())
# x = input()
# s = x[:k] * n
# s = s[:n]
# if int(s) >= int(x):
#     print(n)
#     print(s)
# else:
#     ans = str(int(x[:k]) + 1) * (n // k + 1)
#     print(n)
#     print(ans[:n])

n = int(input())
a = list(map(int, input().split()))
k = 1
white = 0
black = 0
for i in a:
    black += (i // 2) + k * (i % 2)
    white += (i // 2) + (1 - k) * (i % 2)
    k = 1-k
print(min(black, white))
# n,k,t = map(float, input().split())
# x = [0 for i in range(int(n))]
# y = [0 for i in range(int(n))]
# c = [0 for i in range(int(n))]
# dist = []
# for i in range(int(n)):
#     a, b, cl = map(float, input().split())
#     x[i] = a
#     y[i] = b
#     c[i] = int(cl)
# for i in range(int(t)):
#     dist = []
#     clst = [0 for j in range(11)]
#     mx = 0
#     ans = 0
#     a, b = map(float, input().split())
#     for j in range(int(n)):
#         dist.append([((x[j] - a) ** 2 + (y[j] - b) ** 2) ** (1/2), c[j]])
#     dist = sorted(dist, key=lambda tup: tup[0])
#     for j in range(int(k)):
#         clst[dist[j][1]] += 1
#     for j in range(1, len(clst)):
#         if clst[j] > mx:
#             mx = clst[j]
#             ans = j
#     print(ans)
#
#
#
# print(8000**5)

# s = input()
# k = 0
# for i in range(len(s) // 2):
#     if s[i] != s[-i-1]:
#         k = k + 1
# if k == 0:
#     print(0)
# else:
#     print(k-1)

#
# def check_one(s):
#     for j in range((len(s) + 1) // 2, len(s)):
#         if s[0:j] == s[len(s) - j:len(s)+1]:
#             return 1
#     return 0
#
#
# st = input()
# k = 0
# for i in range(2, len(st) + 1):
#     k += check_one(st[0:i])
# print(k)
