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 C {
 
    public static void main(String[] args) throws Exception {
        // FileInputStream inputStream = new FileInputStream("input.txt");
        // FileOutputStream outputStream = new FileOutputStream("output.txt");
 
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
         
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
 
        Solver solver = new Solver();     
        // int t = in.nextInt();
        int t = 1;
        for (int i = 0 ; i < t ; i++) {
            solver.solve(1, in, out);    
        }
        
                 
        out.close();
    }
 
    static class Solver {
 
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            long black, white;
            black = white = 0;
            for (int i = 0 ; i < n ; i++) {
                long x = in.nextLong();
                if (i % 2 == 0) {   
                    long _black = (x + 1) / 2;
                    long _white = x - _black;
                    black += _black;
                    white += _white;                    
                } else {
                    long _black = x / 2;
                    long _white = x - _black;
                    black += _black;
                    white += _white;
                }
            }
            out.println(Math.min(black, white));
        }
    }
   
 
    static class InputReader {
 
        public BufferedReader reader;
        public StringTokenizer tokenizer;
 
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
 
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
 
        public int nextInt() {
            return Integer.parseInt(next());
        }
 
        public long nextLong() {
            return Long.parseLong(next());
        }
 
        public double nextDouble() {
            return Double.parseDouble(next());
        }
 
        public float nextFloat() {
            return Float.parseFloat(next());
        }
    }
}