#include <bits/stdc++.h>
using namespace std;
long long int fact(long long int n) {
  if (n == 1 || n == 0) return 1;
  return n * fact(n - 1);
}
long long int isPrime(long long int n) {
  if (n < 2) return 0;
  if (n < 4) return 1;
  if (n % 2 == 0 or n % 3 == 0) return 0;
  for (long long int i = 5; i * i <= n; i += 6)
    if (n % i == 0 or n % (i + 2) == 0) return 0;
  return 1;
}
long long int modexpo(long long int x, long long int p) {
  long long int res = 1;
  x = x % 1000000007;
  while (p) {
    if (p % 2) res = res * x;
    p >>= 1;
    x = x * x % 1000000007;
    res %= 1000000007;
  }
  return res;
}
long long int binSearch(long long int a[], long long int l, long long int h,
                        long long int x) {
  long long int c = -1;
  while (l <= h) {
    long long int m = (l + h) / 2;
    if (a[m] >= x) {
      c = m;
      h = m - 1;
    } else
      l = m + 1;
  }
  return c;
}
void pairsort(long long int a[], long long int b[], long long int n) {
  pair<long long int, long long int> pairt[n];
  for (long long int i = 0; i < n; i++) {
    pairt[i].first = a[i];
    pairt[i].second = b[i];
  }
  sort(pairt, pairt + n);
  for (long long int i = 0; i < n; i++) {
    a[i] = pairt[i].first;
    b[i] = pairt[i].second;
  }
}
void rev_pairsort(long long int a[], long long int b[], long long int n) {
  pair<long long int, long long int> pairt[n];
  for (long long int i = 0; i < n; i++) {
    pairt[i].first = a[i];
    pairt[i].second = b[i];
  }
  sort(pairt, pairt + n);
  reverse(pairt, pairt + n);
  for (long long int i = 0; i < n; i++) {
    a[i] = pairt[i].first;
    b[i] = pairt[i].second;
  }
}
long long int nod(long long int n) {
  long long int c = 0;
  while (n > 0) {
    c++;
    n /= 10;
  }
  return c;
}
long long int sod(long long int n) {
  long long int s = 0;
  while (n > 0) {
    s += n % 10;
    n /= 10;
  }
  return s;
}
long long int mulmod(long long int a, long long int b) {
  long long int res = 0;
  a = a % 1000000007;
  while (b > 0) {
    if (b % 2 == 1) res = (res + a) % 1000000007;
    a = (a * 2) % 1000000007;
    b /= 2;
  }
  return res % 1000000007;
}
string intToString(long long int n) {
  string s = "";
  while (n > 0) {
    s += char(n % 10 + '0');
    n /= 10;
  }
  reverse(s.begin(), s.end());
  return s;
}
int myComp(int x, int y) {
  if (x < y && x % 2 != y % 2) return 1;
  return 0;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long int q, n, t, m, k = 1, i, j, f = 0, g = 0, h = 1, sum = 0, ans = 0,
                            x, y, l, prev;
  cin >> n;
  long long int a[n];
  for (i = 0; i < n; i++) cin >> a[i];
  long long int ec = 0;
  j = 0;
  long long int ans2 = 0;
  for (i = 0; i < n; i++) {
    if (i % 2) {
      ans += a[i] / 2;
      ans2 += (a[i] + 1) / 2;
    } else {
      ans += (a[i] + 1) / 2;
      ans2 += a[i] / 2;
    }
  }
  cout << min(ans2, ans);
}

### Prompt

In CPP, your task is to solve the following problem:

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>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long int fact(long long int n) {
  if (n == 1 || n == 0) return 1;
  return n * fact(n - 1);
}
long long int isPrime(long long int n) {
  if (n < 2) return 0;
  if (n < 4) return 1;
  if (n % 2 == 0 or n % 3 == 0) return 0;
  for (long long int i = 5; i * i <= n; i += 6)
    if (n % i == 0 or n % (i + 2) == 0) return 0;
  return 1;
}
long long int modexpo(long long int x, long long int p) {
  long long int res = 1;
  x = x % 1000000007;
  while (p) {
    if (p % 2) res = res * x;
    p >>= 1;
    x = x * x % 1000000007;
    res %= 1000000007;
  }
  return res;
}
long long int binSearch(long long int a[], long long int l, long long int h,
                        long long int x) {
  long long int c = -1;
  while (l <= h) {
    long long int m = (l + h) / 2;
    if (a[m] >= x) {
      c = m;
      h = m - 1;
    } else
      l = m + 1;
  }
  return c;
}
void pairsort(long long int a[], long long int b[], long long int n) {
  pair<long long int, long long int> pairt[n];
  for (long long int i = 0; i < n; i++) {
    pairt[i].first = a[i];
    pairt[i].second = b[i];
  }
  sort(pairt, pairt + n);
  for (long long int i = 0; i < n; i++) {
    a[i] = pairt[i].first;
    b[i] = pairt[i].second;
  }
}
void rev_pairsort(long long int a[], long long int b[], long long int n) {
  pair<long long int, long long int> pairt[n];
  for (long long int i = 0; i < n; i++) {
    pairt[i].first = a[i];
    pairt[i].second = b[i];
  }
  sort(pairt, pairt + n);
  reverse(pairt, pairt + n);
  for (long long int i = 0; i < n; i++) {
    a[i] = pairt[i].first;
    b[i] = pairt[i].second;
  }
}
long long int nod(long long int n) {
  long long int c = 0;
  while (n > 0) {
    c++;
    n /= 10;
  }
  return c;
}
long long int sod(long long int n) {
  long long int s = 0;
  while (n > 0) {
    s += n % 10;
    n /= 10;
  }
  return s;
}
long long int mulmod(long long int a, long long int b) {
  long long int res = 0;
  a = a % 1000000007;
  while (b > 0) {
    if (b % 2 == 1) res = (res + a) % 1000000007;
    a = (a * 2) % 1000000007;
    b /= 2;
  }
  return res % 1000000007;
}
string intToString(long long int n) {
  string s = "";
  while (n > 0) {
    s += char(n % 10 + '0');
    n /= 10;
  }
  reverse(s.begin(), s.end());
  return s;
}
int myComp(int x, int y) {
  if (x < y && x % 2 != y % 2) return 1;
  return 0;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long int q, n, t, m, k = 1, i, j, f = 0, g = 0, h = 1, sum = 0, ans = 0,
                            x, y, l, prev;
  cin >> n;
  long long int a[n];
  for (i = 0; i < n; i++) cin >> a[i];
  long long int ec = 0;
  j = 0;
  long long int ans2 = 0;
  for (i = 0; i < n; i++) {
    if (i % 2) {
      ans += a[i] / 2;
      ans2 += (a[i] + 1) / 2;
    } else {
      ans += (a[i] + 1) / 2;
      ans2 += a[i] / 2;
    }
  }
  cout << min(ans2, ans);
}

```