#include <bits/stdc++.h>
using namespace std;
int64_t bs(vector<int64_t>& v, int64_t k, int64_t n) {
  int64_t ans = -1;
  int64_t l = 0, h = n - 1;
  while (l <= h) {
    int64_t mid = (l + (h - l) / 2);
    if (v[mid] >= k) {
      ans = mid;
      h = mid - 1;
    } else
      l = mid + 1;
  }
  return ans;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int64_t n;
  cin >> n;
  vector<int64_t> v(n);
  for (int64_t i = 0; i < n; i++) {
    cin >> v[i];
  }
  sort(v.begin(), v.end());
  int64_t b = 0, w = 0, prev = 0;
  for (int64_t i = 1; i <= 300000; i++) {
    int64_t idx = bs(v, i, n);
    if (idx != -1) {
      int64_t cnt = n - idx;
      if (prev) {
        w += (cnt / 2) + (cnt % 2);
        b += (cnt / 2);
      } else {
        b += (cnt / 2) + (cnt % 2);
        w += (cnt / 2);
      }
      prev = 1 - prev;
    } else
      break;
  }
  cout << min(w, b) << "\n";
  return 0;
}

### 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;
int64_t bs(vector<int64_t>& v, int64_t k, int64_t n) {
  int64_t ans = -1;
  int64_t l = 0, h = n - 1;
  while (l <= h) {
    int64_t mid = (l + (h - l) / 2);
    if (v[mid] >= k) {
      ans = mid;
      h = mid - 1;
    } else
      l = mid + 1;
  }
  return ans;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int64_t n;
  cin >> n;
  vector<int64_t> v(n);
  for (int64_t i = 0; i < n; i++) {
    cin >> v[i];
  }
  sort(v.begin(), v.end());
  int64_t b = 0, w = 0, prev = 0;
  for (int64_t i = 1; i <= 300000; i++) {
    int64_t idx = bs(v, i, n);
    if (idx != -1) {
      int64_t cnt = n - idx;
      if (prev) {
        w += (cnt / 2) + (cnt % 2);
        b += (cnt / 2);
      } else {
        b += (cnt / 2) + (cnt % 2);
        w += (cnt / 2);
      }
      prev = 1 - prev;
    } else
      break;
  }
  cout << min(w, b) << "\n";
  return 0;
}

```