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 INF = 1e18;
clock_t time_p = clock();
void rtime() {
  time_p = clock() - time_p;
  cout << "\nTime Taken : " << fixed << (float)(time_p) / CLOCKS_PER_SEC
       << "s\n";
}
inline long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
inline long long lcm(long long a, long long b) { return (a / gcd(a, b) * b); }
inline long long ncr(long long n, long long r) {
  long long res = 1;
  if (r > n - r) r = n - r;
  for (long long i = 0; i < r; i++) {
    res *= n - i;
    res /= i + 1;
  }
  return res;
}
inline bool prime(long long n) {
  long long i;
  for (i = 2; i <= sqrt(n); i++) {
    if (n % i == 0) return false;
  }
  return true;
}
template <class T>
ostream& operator<<(ostream& os, string V) {
  os << "[ ";
  for (auto v : V) os << v << " ";
  return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, vector<T> V) {
  os << "[ ";
  for (auto v : V) os << v << " ";
  return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, set<T> S) {
  os << "{ ";
  for (auto s : S) os << s << " ";
  return os << "}";
}
template <class T, class T1>
ostream& operator<<(ostream& os, map<T, T1> S) {
  os << "{ ";
  for (auto s : S) os << "(" << s.first << "," << s.second << ") ";
  return os << "}";
}
template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> P) {
  return os << "(" << P.first << "," << P.second << ")";
}
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
const long long mod = 998244353;
inline long long add(long long x, long long y) {
  x += y;
  if (x >= mod) return x - mod;
  return x % mod;
}
inline long long sub(long long x, long long y) {
  x -= y;
  if (x < 0) return x + mod;
  return x;
}
inline long long mul(long long x, long long y) { return (x * 1ll * y) % mod; }
inline long long expo(long long x, long long y) {
  long long ans = 1;
  while (y) {
    if (y & 1) ans = mul(ans, x);
    x = mul(x, x);
    y >>= 1;
  }
  return ans % mod;
}
inline long long inv(long long x) { return expo(x, mod - 2); }
long long rr[] = {0, 1, 1, 1, 0, -1, -1, -1};
long long cc[] = {1, 1, 0, -1, -1, -1, 0, 1};
long long n, m, k, x, y, z, q, a[5 * 100000 + 10], p[5 * 100000 + 10];
void solve() {
  cin >> n;
  for (long long i = 1; i < (long long)n + 1; i++) cin >> a[i];
  long long ans = 0, w = 0, b = 0;
  for (long long i = 1; i < (long long)n + 1; i++) {
    w += a[i] / 2;
    b += a[i] / 2;
    if (a[i] % 2) {
      if (i % 2)
        w++;
      else
        b++;
    }
  }
  cout << min(w, b);
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long t;
  t = 1;
  for (long long i = 1; i <= t; i++) {
    solve();
  }
}
