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.*;
import java.util.*;

public class Task1268B {
    private static InputReader in;
    private static PrintWriter out;
    private static boolean autoFlush = false;
    static final int inf = (int) 1e9 + 7;
    static final long infL = (long) 1e18 + 7;

    static class Testcase {
        public void solve(int test) {
            int n = in.nextInt();
            long even = 0, odd = 0;
            for (int i = 0; i < n; i++) {
                int a = in.nextInt();
                if (a % 2 == 1) {
                    if (i % 2 == 1)
                        odd++;
                    else
                        even++;
                }
                even += a / 2;
                odd += a / 2;
            }
            out.println(Math.min(odd, even));
        }
    }

    public static void main(String[] args) {
        in = new InputReader(System.in);
        out = new PrintWriter(System.out, autoFlush);
        int t = 1;
        // t = in.nextInt();
        for (int i = 1; i <= t; i++) {
            Testcase solver = new Testcase();
            // out.printf("Case #%d: ", i);
            solver.solve(i);
        }
        out.close();
    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public InputReader(FileReader file) throws FileNotFoundException {
            reader = new BufferedReader(file, 32768);
            tokenizer = null;
        }

        public String readLine() {
            String str = "";
            try {
                str = reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return str;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens())
                tokenizer = new StringTokenizer(readLine());
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public float nextFloat() {
            return Float.parseFloat(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    public static void trace(Object... o) {
        System.err.println(Arrays.deepToString(o));
    }
}
