You are given a Young diagram. 

Given diagram is a histogram with $n$ columns of lengths $a_1, a_2, \ldots, a_n$ ($a_1 \geq a_2 \geq \ldots \geq a_n \geq 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 \times 2$ or $2 \times 1$ rectangle.


-----Input-----

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

The next line of input contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 300\,000, a_i \geq 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] $\square$

Difficulty: competition

Starter code:

Solutions:
import sys
readline = sys.stdin.readline

N = int(readline())
A = list(map(int, readline().split()))
BW = [0, 0]
for i in range(N):
    a = A[i]
    BW[i%2] += a//2
    BW[(i+1)%2] += -(-a//2)
print(min(BW))


import sys
input = sys.stdin.readline

n=int(input())
A=list(map(int,input().split()))
B=0
C=0
D=0
E=0

for i in range(n):
    a=A[i]

    if i%2==0:
        B+=a//2
        C+=a-a//2
        D+=a-a//2
        E+=a//2

    else:
        B+=a-a//2
        C+=a//2
        D+=a//2
        E+=a-a//2

print(max(min(B,C),min(D,E)))
        
        


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

ans = 0
black = 0
white = 0
for i in range(n):
    if i % 2 == 0:
        black += a[i] // 2
        white += a[i] - a[i] // 2
    elif i % 2 == 1:
        white += a[i] // 2
        black += a[i] - a[i] // 2

print(min(white, black))

n = input()
l = list(map(int,input().split()))
x = 0
y = 0
for i in l:
    x+=i//2
    y+=(i+1)//2
    x,y=y,x
print(min(x,y))

def find(A):
    ##A is a list of non-increasing number
    on=1
    ans=0
    for x in A:
        if on==1:
            ans+=x//2+x%2
            on=0
        else:
            ans+=x//2
            on=1
    return min(ans,sum(A)-ans)
n=int(input())
A=list(map(int,input().strip().split()))
print(find(A))

n,x,y = int(input()),0,0
l = list(map(int,input().split()))
for a in l: x,y = y+(a//2),x+((a+1)//2);
print(min(x,y))