#include <iostream>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;

int log2_int(ll x) {
  int cur = 0;
  while (true) {
    if (x < 1LL << cur) {
      return cur - 1;
    }
    cur += 1;
  }
}

// This solution was implemented after the author read the editorial.
ll solve(const VL &a) {
  int n = a.size();
  VI b(n + 2), c(n + 2);
  REP(i, 0, n) {
    b[i + 1] = log2_int(a[i]);
    c[i + 1] = log2_int(a[i] - 1) + 1;
  }
  vector<VI> dp(n + 2, VI(2, 0));
  REP(i, 1, n + 2) {
    REP(y, 0, 2) {
      int next = y ? c[i] : b[i];
      int mi = 1e8;
      REP(x, 0, 2) {
	int prev = x ? b[i - 1] : c[i - 1];
	mi = min(mi, dp[i - 1][x] + abs(next - prev) + abs(b[i] - c[i]));
      }
      dp[i][y] = mi;
    }
  }
  return min(dp[n + 1][0], dp[n + 1][1]);
}


int main(void) {
  int n;
  cin >> n;
  VL a(n);
  REP(i, 0, n) {
    cin >> a[i];
  }
  cout << solve(a) / 2 << endl;
}

### Prompt

Your task is to create a Cpp solution to the following problem:

There are A slimes lining up in a row. Initially, the sizes of the slimes are all 1.

Snuke can repeatedly perform the following operation.

* Choose a positive even number M. Then, select M consecutive slimes and form M / 2 pairs from those slimes as follows: pair the 1-st and 2-nd of them from the left, the 3-rd and 4-th of them, ..., the (M-1)-th and M-th of them. Combine each pair of slimes into one larger slime. Here, the size of a combined slime is the sum of the individual slimes before combination. The order of the M / 2 combined slimes remain the same as the M / 2 pairs of slimes before combination.



Snuke wants to get to the situation where there are exactly N slimes, and the size of the i-th (1 ≤ i ≤ N) slime from the left is a_i. Find the minimum number of operations required to achieve his goal.

Note that A is not directly given as input. Assume A = a_1 + a_2 + ... + a_N.

Constraints

* 1 ≤ N ≤ 10^5
* a_i is an integer.
* 1 ≤ a_i ≤ 10^9

Input

Input is given from Standard Input in the following format:


N
a_1 a_2 ... a_N


Output

Print the minimum number of operations required to achieve Snuke's goal.

Examples

Input

2
3 3


Output

2


Input

4
2 1 2 2


Output

2


Input

1
1


Output

0


Input

10
3 1 4 1 5 9 2 6 5 3


Output

10

### Response

```cpp
#include <iostream>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;

int log2_int(ll x) {
  int cur = 0;
  while (true) {
    if (x < 1LL << cur) {
      return cur - 1;
    }
    cur += 1;
  }
}

// This solution was implemented after the author read the editorial.
ll solve(const VL &a) {
  int n = a.size();
  VI b(n + 2), c(n + 2);
  REP(i, 0, n) {
    b[i + 1] = log2_int(a[i]);
    c[i + 1] = log2_int(a[i] - 1) + 1;
  }
  vector<VI> dp(n + 2, VI(2, 0));
  REP(i, 1, n + 2) {
    REP(y, 0, 2) {
      int next = y ? c[i] : b[i];
      int mi = 1e8;
      REP(x, 0, 2) {
	int prev = x ? b[i - 1] : c[i - 1];
	mi = min(mi, dp[i - 1][x] + abs(next - prev) + abs(b[i] - c[i]));
      }
      dp[i][y] = mi;
    }
  }
  return min(dp[n + 1][0], dp[n + 1][1]);
}


int main(void) {
  int n;
  cin >> n;
  VL a(n);
  REP(i, 0, n) {
    cin >> a[i];
  }
  cout << solve(a) / 2 << endl;
}

```