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

// written by luchy0120

public class Main {
    public static void main(String[] args) throws Exception {

        new Main().run();
    }

    static int groups = 0;
    static int[] fa;
    static int[] sz;

    static void init(int n) {
        groups = n;
        fa = new int[n];
        for (int i = 1; i < n; ++i) {
            fa[i] = i;
        }
        sz = new int[n];
        Arrays.fill(sz, 1);
    }

    static int root(int p) {
        while (p != fa[p]) {
            fa[p] = fa[fa[p]];
            p = fa[p];
        }
        return p;
    }

    static void combine(int p, int q) {
        int i = root(p);
        int j = root(q);
        if (i == j) {
            return;
        }
        if (sz[i] < sz[j]) {
            fa[i] = j;
            sz[j] += sz[i];
        } else {
            fa[j] = i;
            sz[i] += sz[j];
        }
        groups--;
    }


    int color[],dfn[],low[],stack[],cnt[];
    boolean vis[];
    boolean iscut[];
    int deep,top,n,m,sum,ans;
    List<Integer> g[];

    void tarjan(int u,int fa)
    {
        int child = 0;
        dfn[u]=++deep;
        low[u]=deep;
        vis[u]=true;
        stack[++top]=u;
        int sz=g[u].size();
        for(int i=0;i<sz;i++)
        {
            int v =g[u].get(i);
            if(v==fa) continue;
            if(dfn[v]==0)
            {
                child++;
                tarjan(v,u);
                low[u]=Math.min(low[u],low[v]);

            }
            else
            {
                if(vis[v])
                {
                    low[u]=Math.min(low[u],low[v]);
                }
            }
        }
        if(fa<0&&child==1){
            iscut[u] =true;
        }

        if(dfn[u]==low[u])
        {
            iscut[u] = true;
            color[u]=++sum;
            vis[u]=false;
            while(stack[top]!=u)
            {
                color[stack[top]]=sum;
                vis[stack[top--]]=false;
            }
            top--;
        }
    }


//    void solve() {
//
//    }




//    int get_room(int i,int j){
//        return i/3*3 + j/3;
//    }

//    int a[][] = new int[9][9];
//    int space = 0;
//
//    boolean vis_row[][] = new boolean[9][10];
//    boolean vis_col[][] = new boolean[9][10];
//    boolean vis_room[][] = new boolean[9][10];
//    int val[][][] =new int[9][9][];
//    int prepare[][];
//
//    void dfs(int rt){
//
//    }

    int h[],to[],ne[];int ct =0;
    void add(int u,int v){
        u--;v--;
        to[ct] = v;
        ne[ct] = h[u];
        h[u] = ct++;

    }



    void solve(){
        int n = ni();
        long a[] = nal(n);

        long x = 0;
        long y = 0;

        for(int i=0;i<n;++i) {
            if(i%2==0){
                x++;
                a[i]--;
                x += a[i]/2;
                y += a[i]/2;
                if(a[i]%2==1){
                    y++;
                }
            }else{
                y++;
                a[i]--;
                x += a[i]/2;
                y += a[i]/2;
                if(a[i]%2==1){
                    x++;
                }
            }
        }
        println(Math.min(x,y));

















    }

//    List<Integer> go[];
//    int par[][];
//    int w[][];
//    int gg[][];
//
//    void dfs(int rt,int fa){
//        vis[rt] = true;
//        if(fa!=-1) {
//            par[rt][0] = fa;
//        }
//        for(int to:go[rt]){
//            if(to==fa) continue;
//            w[to][0] = gg[rt][to];
//            dfs(to,rt);
//        }
//    }
//
//
//    void solve() {
//           int n = ni();
//           int m = ni();
//
//           int e[][] = new int[m][3];
//           for(int i=0;i<m;++i){
//               int u = ni();
//               int v = ni();
//               int z = ni();
//               e[i][0] = u;
//               e[i][1] = v;
//               e[i][2] = z;
//           }
//
//           Arrays.sort(e,(xx,yy)->{
//               return yy[2]-xx[2];
//           });
//           init(n+1);
//
//
//            gg = new int[n+1][n+1];
//
//           go = new ArrayList[n+1];
//
//           for(int i=0;i<=n;++i){
//               go[i] = new ArrayList<>();
//           }
//
//           for(int i=0;i<m;++i){
//                int p1 = e[i][0];
//                int p2 = e[i][1];
//                if(root(p1)!=root(p2)){
//                    combine(p1,p2);
//                    gg[p1][p2] = e[i][2];
//                    gg[p2][p1] = e[i][2];
//                    go[p1].add(p2);
//                    go[p2].add(p1);
//                }
//           }
//           boolean vis[] = new boolean[n+1];
//           par = new int[n+1][21];
//           w = new int[n+1][21];
//
//        for(int j=0;j<21;++j) {
//            for (int i = 0; i <= n; ++i) {
//                w[i][j] = 100000000;
//            }
//        }
//
//           for(int i=0;i<=n;++i){
//               if(!vis[i]){
//                   dfs(i,-1);
//               }
//           }
//
//           for(int j=1;j<20;++j){
//               for(int i=1;i<=n;++i){
//                   w[i][j] = Math.min(w[i][j-1],w[par[i][j-1]][j-1]);
//                   par[i][j] = par[par[i][j-1]][j-1];
//               }
//           }
//
//           int q =ni();
//
//           for(int i=0;i<q;++i){
//               int xx = ni();
//               int yy = ni();
//               if(root(xx)!=root(yy)){
//                   println(-1); continue;
//               }
//                int res = Integer.MAX_VALUE;
//               for(int p=20;p>=0;--p){
//                   if(par[xx][p]!=par[yy][p]){
//                       res = Math.min(res,w[xx][p]);
//                       res = Math.min(res,w[yy][p]);
//                       xx = par[xx][p];
//                       yy = par[yy][p];
//                   }
//               }
//               res = Math.min(res,w[xx][0]);
//               res = Math.min(res,w[yy][0]);
//               println(res);
//
//           }
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//    }


    static long mul(long a, long b, long p)
    {
        long res=0,base=a;
        while(b>0)
        {
            if((b&1L)>0)
                res=(res+base)%p;
            base=(base+base)%p;
            b>>=1;
        }
        return res;
    }


    static long mod_pow(long k,long n,long p){
        long res = 1L;
        long temp = (k%p+p)%p;
        while(n!=0L){
            if((n&1L)==1L){
                res = ((res*temp)%p+p)%p;
            }
            temp = ((temp * temp)%p+p)%p;
            n = n>>1L;
        }
        return res%p;
    }
    public static String roundS(double result, int scale){
        String fmt = String.format("%%.%df", scale);
        return String.format(fmt, result);
    }


//    void solve() {
//
//        for(int i=0;i<9;++i) {
//            for (int j = 0; j < 9; ++j) {
//                int v = ni();
//                a[i][j] = v;
//                if(v>0) {
//                    vis_row[i][v] = true;
//                    vis_col[j][v] = true;
//                    vis_room[get_room(i, j)][v] = true;
//                }else{
//                    space++;
//                }
//            }
//        }
//
//
//        prepare = new int[space][2];
//
//        int p = 0;
//
//        for(int i=0;i<9;++i) {
//            for (int j = 0; j < 9; ++j) {
//                if(a[i][j]==0){
//                    prepare[p][0] = i;
//                    prepare[p][1]= j;p++;
//                    List<Integer> temp =new ArrayList<>();
//                    for(int k=1;k<=9;++k){
//                        if(!vis_col[j][k]&&!vis_row[i][k]&&!vis_room[get_room(i,j)][k]){
//                            temp.add(k);
//                        }
//                    }
//                    int sz = temp.size();
//                    val[i][j] = new int[sz];
//                    for(int k=0;k<sz;++k){
//                        val[i][j][k] = temp.get(k);
//                    }
//                }
//            }
//        }
//        Arrays.sort(prepare,(x,y)->{
//           return Integer.compare(val[x[0]][x[1]].length,val[y[0]][y[1]].length);
//        });
//        dfs(0);
//
//
//
//
//
//
//
//
//
//
//    }




    InputStream is;
    PrintWriter out;

    void run() throws Exception {
        is = System.in;
        out = new PrintWriter(System.out);
        solve();
        out.flush();
    }

    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;

    private int readByte() {
        if (lenbuf == -1) throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {
                lenbuf = is.read(inbuf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (lenbuf <= 0) return -1;
        }
        return inbuf[ptrbuf++];
    }

    private boolean isSpaceChar(int c) {
        return !(c >= 33 && c <= 126);
    }

    private int skip() {
        int b;
        while ((b = readByte()) != -1 && isSpaceChar(b)) ;
        return b;
    }

    private double nd() {
        return Double.parseDouble(ns());
    }

    private char nc() {
        return (char) skip();
    }

    private char ncc() {
        int b = readByte();
        return (char) b;
    }

    private String ns() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private char[] ns(int n) {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) {
            buf[p++] = (char) b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }

    private String nline() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while (!isSpaceChar(b) || b == ' ') {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private char[][] nm(int n, int m) {
        char[][] a = new char[n][];
        for (int i = 0; i < n; i++) a[i] = ns(m);
        return a;
    }

    private int[] na(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = ni();
        return a;
    }

    private long[] nal(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = nl();
        return a;
    }

    private int ni() {
        int num = 0, b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) {
        }
        ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        while (true) {
            if (b >= '0' && b <= '9') num = (num << 3) + (num << 1) + (b - '0');
            else return minus ? -num : num;
            b = readByte();
        }
    }

    private long nl() {
        long num = 0;
        int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) {
        }
        ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        while (true) {
            if (b >= '0' && b <= '9') num = num * 10 + (b - '0');
            else return minus ? -num : num;
            b = readByte();
        }
    }

    void print(Object obj) {
        out.print(obj);
    }

    void println(Object obj) {
        out.println(obj);
    }

    void println() {
        out.println();
    }

    void printArray(int a[],int from){
        int l = a.length;
        for(int i=from;i<l;++i){
            print(a[i]);
            if(i!=l-1){
                print(" ");
            }
        }
        println();
    }

    void printArray(long a[],int from){
        int l = a.length;
        for(int i=from;i<l;++i){
            print(a[i]);
            if(i!=l-1){
                print(" ");
            }
        }
        println();
    }
}