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.*;
import java.io.*;
 
public class Main2 {
	static class FastReader{ 
        BufferedReader br; 
        StringTokenizer st; 
        public FastReader(){br = new BufferedReader(new InputStreamReader(System.in));}
        String next(){while (st == null || !st.hasMoreElements()){try{st = new StringTokenizer(br.readLine());} 
        catch (IOException  e){e.printStackTrace();}}return st.nextToken();}
        int nextInt(){ return Integer.parseInt(next());}long nextLong(){return Long.parseLong(next());}double nextDouble(){return Double.parseDouble(next());}
        String nextLine(){String str = ""; try{str = br.readLine(); } catch (IOException e) {e.printStackTrace();} return str; } 
    }
	static int mod = (int)(1e9+7);
	static FastReader sc = new FastReader();
	static PrintWriter out = new PrintWriter(System.out);
	public static void main (String[] args) {
		int t = 1;
//    	t = sc.nextInt();
	    z : while(t-->0) {
	    	int n = sc.nextInt();
	    	long ans[] = new long[2];
	    	long x = 0;
	    	for(int i=0;i<n;i++) {
	    		x = sc.nextInt();
	    		ans[i%2] += x/2;
	    		x++;
	    		ans[(i+1)%2] += x/2;
	    	}
	    	out.write(Math.min(ans[0], ans[1])+"");
		}
		out.close();
	}
}