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>
// Utilities
import java.io.*;
import java.util.*;
 
public class Main {
  static int N;
  static int[] a;
  static long x = 0, y = 0;
 
  public static void main(String[] args) throws IOException {
    INPUT in = new INPUT(System.in);
    N = in.iscan();
    int a;
    for (int i = 0; i < N; i++) {
      a = in.iscan();
      if (i % 2 == 0){
        x += a % 2 == 1 ? a / 2 + 1 : a / 2;
        y += a / 2;
      }
      else {
        x += a / 2;
        y += a % 2 == 1 ? a / 2 + 1 : a / 2;
      }
    }
    System.out.println(Math.min(x, y));
  }
 
  private static class INPUT {
 
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar, numChars;
 
		public INPUT (InputStream stream) {
			this.stream = stream;
		}
 
		public INPUT (String file) throws IOException {
			this.stream = new FileInputStream (file);
		}
 
		public int cscan () throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read (buf);
			}
			
			if (numChars == -1)
				return numChars;
 
			return buf[curChar++];
		}
 
		public int iscan () throws IOException {
			int c = cscan (), sgn = 1;
			
			while (space (c))
				c = cscan ();
 
			if (c == '-') {
				sgn = -1;
				c = cscan ();
			}
 
			int res = 0;
 
			do {
				res = (res << 1) + (res << 3);
				res += c - '0';
				c = cscan ();
			}
			while (!space (c));
 
			return res * sgn;
		}
 
		public String sscan () throws IOException {
			int c = cscan ();
			
			while (space (c))
				c = cscan ();
 
			StringBuilder res = new StringBuilder ();
 
			do {
				res.appendCodePoint (c);
				c = cscan ();
			}
			while (!space (c));
 
			return res.toString ();
		}
 
		public double dscan () throws IOException {
			int c = cscan (), sgn = 1;
			
			while (space (c))
				c = cscan ();
 
			if (c == '-') {
				sgn = -1;
				c = cscan ();
			}
 
			double res = 0;
 
			while (!space (c) && c != '.') {
				if (c == 'e' || c == 'E')
					return res * UTILITIES.fast_pow (10, iscan ());
				
				res *= 10;
				res += c - '0';
				c = cscan ();
			}
 
			if (c == '.') {
				c = cscan ();
				double m = 1;
 
				while (!space (c)) {
					if (c == 'e' || c == 'E')
						return res * UTILITIES.fast_pow (10, iscan ());
 
					m /= 10;
					res += (c - '0') * m;
					c = cscan ();
				}
			}
 
			return res * sgn;
		}
 
		public long lscan () throws IOException {
			int c = cscan (), sgn = 1;
			
			while (space (c))
				c = cscan ();
 
			if (c == '-') {
				sgn = -1;
				c = cscan ();
			}
 
			long res = 0;
 
			do {
				res = (res << 1) + (res << 3);
				res += c - '0';
				c = cscan ();
			}
			while (!space (c));
 
			return res * sgn;
		}
 
		public boolean space (int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}
 
	public static class UTILITIES {
 
		static final double EPS = 10e-6;
 
		public static int lower_bound (int[] arr, int x) {
			int low = 0, high = arr.length, mid = -1;
 
			while (low < high) {
				mid = (low + high) / 2;
 
				if (arr[mid] >= x)
					high = mid;
				else
					low = mid + 1;
			}
 
			return low;
		}
 
		public static int upper_bound (int[] arr, int x) {
			int low = 0, high = arr.length, mid = -1;
 
			while (low < high) {
				mid = (low + high) / 2;
 
				if (arr[mid] > x)
					high = mid;
				else
					low = mid + 1;
			}
 
			return low;
		}
 
		public static int gcd (int a, int b) {
			return b == 0 ? a : gcd (b, a % b);
		}
 
		public static int lcm (int a, int b) {
			return a * b / gcd (a, b);
		}
 
		public static int fast_pow_mod (int b, int x, int mod) {
			if (x == 0) return 1;
			if (x == 1) return b;
			if (x % 2 == 0) return fast_pow_mod (b * b % mod, x / 2, mod) % mod;
 
			return b * fast_pow_mod (b * b % mod, x / 2, mod) % mod;
		}
 
		public static int fast_pow (int b, int x) {
			if (x == 0) return 1;
			if (x == 1) return b;
			if (x % 2 == 0) return fast_pow (b * b, x / 2);
 
			return b * fast_pow (b * b, x / 2);
		}
 
		public static long choose (long n, long k) {
			k = Math.min (k, n - k);
			long val = 1;
 
			for (int i = 0; i < k; ++i)
				val = val * (n - i) / (i + 1);
 
			return val;
		}
 
		public static long permute (int n, int k) {
			if (n < k) return 0;
			long val = 1;
 
			for (int i = 0; i < k; ++i)
				val = (val * (n - i));
 
			return val;
		}
	}
}