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;
template <class U, class V>
istream &operator>>(istream &is, pair<U, V> &p) {
  return is >> p.first >> p.second;
}
template <class U, class V>
ostream &operator<<(ostream &os, const pair<U, V> &p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <
    class Istream, class Container,
    typename std::enable_if<is_same<Istream, istream>::value, int>::type = 0>
Istream &operator>>(Istream &is, Container &container) {
  for (auto &value : container) is >> value;
  return is;
}
template <
    class Ostream, class Container,
    typename std::enable_if<is_same<Ostream, ostream>::value, int>::type = 0>
Ostream &operator<<(Ostream &os, const Container &container) {
  auto _begin = begin(container), _end = end(container);
  for (auto it = _begin; it != _end;)
    os << "{ "[it != _begin] << *it << ",}"[++it == _end];
  return os;
}
namespace io {
template <class... As>
struct last {};
template <class... As>
using last_t = typename last<As...>::type;
template <class A>
struct last<A> {
  using type = A;
};
template <class A, class... As>
struct last<A, As...> {
  using type = typename last<As...>::type;
};
template <class Z>
Z read(Z &) {
  Z z;
  cin >> z;
  return z;
}
template <class A, class... As>
last_t<As...> read(A &a, As &...as) {
  return cin >> a, read(as...);
}
void log_rest() {}
template <class A, class... As>
void log_rest(const A &a, const As &...as) {
  cerr << ", " << a;
  log_rest(as...);
}
template <class A, class... As>
void log(const string &pref, const A &a, const As &...as) {
  cerr << pref << a, log_rest(as...);
}
}  // namespace io
template <class T>
T make_vec(T default_value) {
  return default_value;
}
template <class T, class Arg, class... Args>
auto make_vec(T default_value, Arg size, Args... rest)
    -> vector<decltype(make_vec(default_value, rest...))> {
  auto level = make_vec(default_value, rest...);
  return vector<decltype(level)>(size, level);
}
template <class Xs>
int sz(const Xs &xs) {
  return static_cast<int>(xs.size());
}
using i64 = int64_t;
using f80 = long double;
using Str = string;
template <class T = int>
using Vec = vector<T>;
template <class K = int, class H = hash<K>>
using US = unordered_set<K, H>;
template <class K, class V, class H = hash<K>>
using UM = unordered_map<K, V, H>;
template <class U = int, class V = U>
using P = pair<U, V>;
using G = Vec<Vec<int>>;
template <class T, class P>
auto bin_search(T l, T r, P p) -> T {
  for (T m; m = (l + r) / 2, m != l && m != r; (p(m) ? l : r) = m)
    ;
  return l;
}
int main() {
  int n = io::read(n);
  Vec<i64> as(n);
  cin >> as;
  i64 black = 0, white = 0;
  for (decltype(n) i = {}; i != n; ++i) {
    black += (as[i] + (i & 1)) / 2;
    white += (as[i] + (1 ^ (i & 1))) / 2;
  }
  cout << min(black, white) << '\n';
}
namespace {
auto fast_io = [] {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(8) << fixed;
  cerr << boolalpha << setprecision(4) << fixed;
  return 0;
}();
}
