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 EdB {

	public static void main(String[] args) throws Exception{
		int num = 998244353;

		// TODO Auto-generated method stub
 		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 		PrintWriter out = new PrintWriter(System.out);
//	 		String input1 = bf.readLine().trim();
//	 		String input2 = bf.readLine().trim();
	 	int n = Integer.parseInt(bf.readLine());
	 	int [] array = new int[n+1];
	 	StringTokenizer st = new StringTokenizer(bf.readLine());
	 	for(int i = 0;i<n;i++){
	 		array[i] = Integer.parseInt(st.nextToken());
	 	}
	 	array[n] = 0;
	 	long[] per = new long[array[0]];
	 	int j = array[0];
	 	int count = 0;
	 	int index = 0;
	 	for(int i = 0;i<n+1;i++){
	 		if (array[i] == j){
	 			count++;
	 		}
	 		else{
	 			per[index] = count;
	 			count++;
	 			index+=(j-array[i]);
	 			j = array[i];
	 		}
	 	}
	 	for(int i = 1;i<array[0];i++){
	 		if (per[i] == 0)
	 			per[i] = per[i-1];
	 	}
	 	long answer = 0;
	 	long white = 0;
	 	long black = 0;
	 	boolean whitestart = true;
	 	for(int i = 0;i<array[0];i++){
	 		if (whitestart){
	 			black+=per[i]/2;
	 			white+=(per[i]-per[i]/2);
	 			whitestart = false;
	 		}
	 		else{
	 			white+=per[i]/2;
	 			black+=(per[i]-per[i]/2);
	 			whitestart = true;
	 		}
	 	}
	 	out.println(Math.min(white,  black));
	 	out.close();
 		
 	}
}
 	
 
//StringJoiner sj = new StringJoiner(" "); 
//sj.add(strings)
//sj.toString() gives string of those stuff w spaces or whatever that sequence is

 		
 		
 		
 		
	


