#include <bits/stdc++.h>
using namespace std;
long long DP[300005];
long long have[300005] = {0};
long long N, all[300005] = {0};
long long Next[300005];
vector<long long> how;
long long F(long long here) {
  if (here >= N) return 0;
  if (have[here]) return DP[here];
  have[here] = 1;
  DP[here] = F(here + 1);
  if (Next[here] < N) DP[here] = max(DP[here], F(Next[here] + 1) + 1);
  return DP[here];
}
int main() {
  long long i, ans = 0, ok = 0, t = 0, last, x = 1000000, y = 1000000, a = 0,
               b = 0;
  scanf("%lld", &N);
  for (i = 0; i < N; i++) {
    scanf("%lld", &all[i]);
    t += all[i] / 2;
    if (all[i] % 2) how.push_back(i);
  }
  N = how.size();
  for (i = 0; i < N; i++) Next[i] = 1000000;
  for (i = N - 1; i >= 0; i--) {
    if (how[i] % 2 == 0)
      a++;
    else
      b++;
  }
  printf("%lld\n", t + min(a, b));
  return 0;
}

### Prompt

Please create a solution in cpp to 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 DP[300005];
long long have[300005] = {0};
long long N, all[300005] = {0};
long long Next[300005];
vector<long long> how;
long long F(long long here) {
  if (here >= N) return 0;
  if (have[here]) return DP[here];
  have[here] = 1;
  DP[here] = F(here + 1);
  if (Next[here] < N) DP[here] = max(DP[here], F(Next[here] + 1) + 1);
  return DP[here];
}
int main() {
  long long i, ans = 0, ok = 0, t = 0, last, x = 1000000, y = 1000000, a = 0,
               b = 0;
  scanf("%lld", &N);
  for (i = 0; i < N; i++) {
    scanf("%lld", &all[i]);
    t += all[i] / 2;
    if (all[i] % 2) how.push_back(i);
  }
  N = how.size();
  for (i = 0; i < N; i++) Next[i] = 1000000;
  for (i = N - 1; i >= 0; i--) {
    if (how[i] % 2 == 0)
      a++;
    else
      b++;
  }
  printf("%lld\n", t + min(a, b));
  return 0;
}

```