#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#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;
typedef pair<int, int> PI;
const ll mod = 1e9 + 7;


ll calc(const VL &a) {
  int n = a.size();
  // all 1?
  bool all_one = true;
  REP(i, 0, n) {
    all_one &= a[i] == 1;
  }
  if (all_one) {
    return 0;
  }
  VL sub(n);
  ll tot = 0;
  int cur = 0;
  REP(i, 0, n) {
    sub[i] = (a[i] + 1) / 2;
    // 0 ... 0 1 -> ok
    // 1 0 ... 0 1 -> Ok
    // 1 0 ... 0 -> ok
    // if it encounters 1, this sector can be completely ignored
    if (a[i] == 1) {
      if (cur > 0) {
	tot += 1;
	cur = 0;
      }
      // else, nothing happens.
      continue;
    }
    if (a[i] % 2 == 1) {
      if (cur == 0) {
	cur = 1;
      } else {
	tot += 1;
	cur = 0;
      }
    } else {
      cur += 1;
    }
  }
  if (cur > 0) {
    tot += 1;
  }
  return tot + calc(sub);
}

map<VL, ll> memo;

ll exact(const VL &a, bool path_rec = false) {
  int n = a.size();
  pair<ll, PI> mi(5e15, PI(-1, -1));
  bool all_one = true;
  REP(i, 0, n) {
    all_one &= a[i] == 1;
  }
  if (all_one) {
    return 0;
  }
  if (not path_rec && memo.count(a)) {
    return memo[a];
  }
  REP(i, 0, n) {
    REP(j, i, n) {
      VL sub(a);
      bool ok = true;
      bool nonone = false;
      REP(k, i, j + 1) {
	sub[k] = (sub[k] + 1) / 2;
	if (k != i && k != j) {
	  if (a[k] % 2 != 0) {
	    ok = false;
	    break;
	  }
	}
	if (a[k] != 1) {
	  nonone = true;
	}
      }
      if (not ok || not nonone) {
	continue;
      }
      ll res = exact(sub);
      mi = min(mi, make_pair(res, PI(i, j)));
    }
  }
  if (path_rec) {
    int u = mi.second.first;
    int v = mi.second.second;
    cerr << "perform " << u << " " << v << endl;
    cerr << "a:";
    REP(i, 0, n) {
      cerr << " " << a[i];
    }
    cerr << endl;
    VL sub(a);
    REP(k, u, v + 1) {
      sub[k] = (sub[k] + 1) / 2;
    }
    exact(sub, true);
  }
  return memo[a] = mi.first + 1;
}

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

Generate 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 <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#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;
typedef pair<int, int> PI;
const ll mod = 1e9 + 7;


ll calc(const VL &a) {
  int n = a.size();
  // all 1?
  bool all_one = true;
  REP(i, 0, n) {
    all_one &= a[i] == 1;
  }
  if (all_one) {
    return 0;
  }
  VL sub(n);
  ll tot = 0;
  int cur = 0;
  REP(i, 0, n) {
    sub[i] = (a[i] + 1) / 2;
    // 0 ... 0 1 -> ok
    // 1 0 ... 0 1 -> Ok
    // 1 0 ... 0 -> ok
    // if it encounters 1, this sector can be completely ignored
    if (a[i] == 1) {
      if (cur > 0) {
	tot += 1;
	cur = 0;
      }
      // else, nothing happens.
      continue;
    }
    if (a[i] % 2 == 1) {
      if (cur == 0) {
	cur = 1;
      } else {
	tot += 1;
	cur = 0;
      }
    } else {
      cur += 1;
    }
  }
  if (cur > 0) {
    tot += 1;
  }
  return tot + calc(sub);
}

map<VL, ll> memo;

ll exact(const VL &a, bool path_rec = false) {
  int n = a.size();
  pair<ll, PI> mi(5e15, PI(-1, -1));
  bool all_one = true;
  REP(i, 0, n) {
    all_one &= a[i] == 1;
  }
  if (all_one) {
    return 0;
  }
  if (not path_rec && memo.count(a)) {
    return memo[a];
  }
  REP(i, 0, n) {
    REP(j, i, n) {
      VL sub(a);
      bool ok = true;
      bool nonone = false;
      REP(k, i, j + 1) {
	sub[k] = (sub[k] + 1) / 2;
	if (k != i && k != j) {
	  if (a[k] % 2 != 0) {
	    ok = false;
	    break;
	  }
	}
	if (a[k] != 1) {
	  nonone = true;
	}
      }
      if (not ok || not nonone) {
	continue;
      }
      ll res = exact(sub);
      mi = min(mi, make_pair(res, PI(i, j)));
    }
  }
  if (path_rec) {
    int u = mi.second.first;
    int v = mi.second.second;
    cerr << "perform " << u << " " << v << endl;
    cerr << "a:";
    REP(i, 0, n) {
      cerr << " " << a[i];
    }
    cerr << endl;
    VL sub(a);
    REP(k, u, v + 1) {
      sub[k] = (sub[k] + 1) / 2;
    }
    exact(sub, true);
  }
  return memo[a] = mi.first + 1;
}

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;
}

```