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>

import java.util.*;

public class test {
	static int N = (int) 2e5 + 99;

	public static class pair implements Comparable<pair> {
		int x;
		int s;

		public pair(int x, int s) {
			this.x = x;
			this.s = s;
		}

		@Override
		public int compareTo(pair o) {
			if (this.x == o.x)
				return this.s - o.s;
			else
				return this.x - o.x;
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int t = 1;// sc.nextInt();

		while (t-- > 0) {

			int n = sc.nextInt();
			int a[]=new int[n];
			for(int i=0;i<n;i++) {
				a[i]=sc.nextInt();
			}
			boolean f=true;
			long b=0;
			long w=0;
			for(int i=0;i<n;i++) {
				if(f) {
					b+=(a[i]+1)/2;
					w+=a[i]-(a[i]+1)/2;
					f=false;
				}
				else {
					w+=(a[i]+1)/2;
					b+=a[i]-(a[i]+1)/2;
					f=true;
				}
			}
			
			
			System.out.println(Math.min(b, w));
		}
	}

	public static void solve(int a[], int k,String s) {
		System.out.println(a.length);
		boolean f = false;
		for (int i = k; i < a.length; i++) {
//			int j = i + k, ans = 0;
//			while (j < a.length) {
//				ans = Math.max(ans, a[j]);
//				j += k;
//			}
//			if (ans > a[i]) {
//
//				f = true;
//				break;
//			}

			a[i]=a[i-k];
		}
		String b = convertArrayToStringMethod(a);
		long val=0;
		for(int i=0;i<a.length;i++) {
			int n=a[i]-(s.charAt(i)-48);
			if(n!=0) {
				
				val=n;break;
			}
		}
	//	long val=b.compareTo(s);
		if (val<0) {

			int c=1;
			for (int i = k - 1; i >= 0; i--) {
				int t=a[i];
				a[i]=(a[i]+c)%10;
				c=(c+t)/10;
			}
			a[0]+=c;


		}
		for(int i=k;i<a.length;i++) {
			a[i]=a[i-k];
		}
		for(int i=0;i<a.length;i++) {
			System.out.print(a[i]);
		}
	}
	
	public static String convertArrayToStringMethod(int[] strArray) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < strArray.length; i++) {
            stringBuilder.append(strArray[i]);
        }
        return stringBuilder.toString();
    }
}
