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>
#include <bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
long long po(long long a, long long b) {
  if (b == 0) return 1 % mod;
  long long y = po(a, b / 2);
  y = y * y % mod;
  if (b % 2 == 1) y = y * a % mod;
  return y;
}
long long inv(long long i) { return po(i, mod - 2); }
struct trie {
  long long cnt;
  trie* ch[2];
  trie() : cnt(0ll) {
    ch[0] = NULL;
    ch[1] = NULL;
  }
};
int n;
int a[300005];
long long ans = 0;
int lst[300005];
void solve() {
  int cr = -1;
  cin >> n;
  for (long long i = (long long)0; i != (long long)n; i = i + 1) cin >> a[i];
  ;
  for (long long i = (long long)0; i != (long long)n; i = i + 1) {
    ans += 1ll * (a[i] / 2);
    a[i] = a[i] % 2;
    if (a[i] == 1) {
      if (cr != -1 && (i - cr) % 2 == 1) {
        ans += 1;
        cr = lst[cr];
        lst[i] = cr;
      } else {
        lst[i] = cr;
        cr = i;
      }
    } else {
      lst[i] = cr;
    }
  }
  cout << ans << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t;
  t = 1;
  while (t--) {
    solve();
  }
}
