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.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
 
public class Main {
	static StreamTokenizer st = new StreamTokenizer(new BufferedInputStream(System.in));
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter pr = new PrintWriter(new BufferedOutputStream(System.out));
	static Scanner sc = new Scanner(System.in);
 
	public static void main(String[] args) {
//		long tic = System.currentTimeMillis();
		int n = nextInt();
		int arr[] = new int[n];
		long ans = 0;
		boolean isodd = false;
		int odnum = 0;
		for (int i = 0; i < n; i++) {
			arr[i] = nextInt();
			ans += arr[i] / 2;
			if (arr[i] % 2 == 1 && isodd) {
				isodd = false;
				odnum -= 1;
				ans++;
			} else if (arr[i] % 2 == 1) {
				odnum++;
				isodd = true;
			} else {
				if (odnum > 0)
					isodd = !isodd;
				else 
					isodd = false;
			}
		}
		System.out.println(ans);
 
//		long toc = System.currentTimeMillis();
//		System.out.println("Elapsed time: " + (toc - tic) + " ms");
	}
 
	private static long A(long n, long k, long mod) {
		long jcn = n;
		for (int i = 1; i < k; i++) {
			jcn *= (n - i);
			jcn %= mod;
		}
		return jcn;
	}
 
	private static long C(long n, long k, long mod) {
		long jcn = n;
		long jck = 1;
		for (int i = 1; i < k; i++) {
			jcn *= (n - i);
			jcn %= mod;
			jck *= i;
			jck %= mod;
		}
		jck *= k;
		jck %= mod;
		return jcn * pow(jck, mod - 2, mod) % mod;
	}
 
	static long pow(long a, long b, long mod) {
		long result = 1;
		while (b > 0) {
			if (b % 2 == 1) {
				result = (result * a) % mod;
			}
			a = (a * a) % mod;
			b /= 2;
		}
		return result;
	}
 
	static int nextInt() {
		try {
			st.nextToken();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return (int) st.nval;
	}
 
	static double nextDouble() {
		try {
			st.nextToken();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return st.nval;
	}
 
	static String next() {
		try {
			st.nextToken();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return st.sval;
	}
 
	static long nextLong() {
		try {
			st.nextToken();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return (long) st.nval;
	}
}