#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <functional>
#include <sstream>
#include <fstream>
#include <valarray>
#include <complex>
#include <queue>
#include <cassert>
#include <bitset>
using namespace std;

#ifdef LOCAL
	#define debug_flag 1
#else
	#define debug_flag 0
#endif

template <class T1, class T2 >
std::ostream& operator << (std::ostream& os, const pair<T1, T2> &p) 
{
	os << "[" << p.first << ", " << p.second << "]";
	return os;
}

template <class T >
std::ostream& operator << (std::ostream& os, const std::vector<T>& v) 
{
	os << "[";
	bool first = true;
	for (typename std::vector<T>::const_iterator it = v.begin(); it != v.end(); ++it)
	{
		if (!first)
			os << ", ";
		first = false;
		os << *it;
	}
	os << "]";
	return os;
}

#define dbg(args...) { if (debug_flag) { _print(_split(#args, ',').begin(), args); cerr << endl; } else { void(0);} }

vector<string> _split(const string& s, char c) {
	vector<string> v;
	stringstream ss(s);
	string x;
	while (getline(ss, x, c))
		v.emplace_back(x);
	return v;
}

void _print(vector<string>::iterator) {}
template<typename T, typename... Args>
void _print(vector<string>::iterator it, T a, Args... args) {
    string name = it -> substr((*it)[0] == ' ', it -> length());
    if (isalpha(name[0]))
	    cerr << name  << " = " << a << " ";
	else
	    cerr << name << " ";
	_print(++it, args...);
}

typedef long long int int64;

const int INF = 1e9;

namespace slow {
  map<vector<int>, int> dp;

  vector<int> apply(const vector<int>&v, int a, int b) {
    vector<int> res;
    for (int i = 0; i < (int)v.size(); i++) {
      if (a <= i && i <= b) {
        res.push_back(v[i] + v[i + 1]);
        i++;
      } else {
        res.push_back(v[i]);
      }
    }
    return res;
  }

  int get_f(const vector<int>& v) {
    if (dp.count(v)) {
      return dp[v];
    }
    
    if (v.size() == 1) {
      return 0;
    }
    int ans = INF;
    for (int i = 0; i < (int)v.size(); i++) {
      for (int j = i + 1; j < (int)v.size(); j += 2) {
        vector<int> to = apply(v, i, j);
        int cur_ans = get_f(to) + 1;
        ans = min(ans, cur_ans);
      }
    }

    return dp[v] = ans;
  }
}

namespace fast {
  int get_log(int x) {
    assert(x >= 1);
    int res = 0;
    while (x > 1) {
      res++;
      x /= 2;
    }
    return res;
  }

  bool is_pow2(int x) {
    while (x % 2 == 0) {
      x /= 2;
    }
    return x == 1;
  }

  int get_op_cnt(int x) {
    int l = get_log(x);
    if (!is_pow2(x)) {
      l++;
    }
    return l;
  }

  int64 solve(vector<int> a_list) {
    int64 ans = 0;
    int op_cnt = 0;
    for (int a : a_list) {
      int need_op_cnt = get_op_cnt(a);
      if (need_op_cnt <= op_cnt) {
        if (is_pow2(a)) {
          op_cnt = need_op_cnt;
        } else {
          op_cnt = need_op_cnt - 1;
        }
      } else {
        ans += need_op_cnt - op_cnt;
        op_cnt = need_op_cnt;
      }
    }
    return ans;
  }
}

void test() {
  for (int i = 1; i <= 10; i++) {
    vector<int> v(i, 1);
    printf("size = %d ans = %d\n", i, slow::get_f(v));
  }
}

void submit() {
  int n;
  scanf("%d", &n);
  vector<int> a_list(n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a_list[i]);
  }
  int64 ans = fast::solve(a_list);
  printf("%lld\n", ans);
}

int main()
{
#ifdef LOCAL
	freopen ("input.txt", "r", stdin);
#endif

  submit();

	return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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 <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <functional>
#include <sstream>
#include <fstream>
#include <valarray>
#include <complex>
#include <queue>
#include <cassert>
#include <bitset>
using namespace std;

#ifdef LOCAL
	#define debug_flag 1
#else
	#define debug_flag 0
#endif

template <class T1, class T2 >
std::ostream& operator << (std::ostream& os, const pair<T1, T2> &p) 
{
	os << "[" << p.first << ", " << p.second << "]";
	return os;
}

template <class T >
std::ostream& operator << (std::ostream& os, const std::vector<T>& v) 
{
	os << "[";
	bool first = true;
	for (typename std::vector<T>::const_iterator it = v.begin(); it != v.end(); ++it)
	{
		if (!first)
			os << ", ";
		first = false;
		os << *it;
	}
	os << "]";
	return os;
}

#define dbg(args...) { if (debug_flag) { _print(_split(#args, ',').begin(), args); cerr << endl; } else { void(0);} }

vector<string> _split(const string& s, char c) {
	vector<string> v;
	stringstream ss(s);
	string x;
	while (getline(ss, x, c))
		v.emplace_back(x);
	return v;
}

void _print(vector<string>::iterator) {}
template<typename T, typename... Args>
void _print(vector<string>::iterator it, T a, Args... args) {
    string name = it -> substr((*it)[0] == ' ', it -> length());
    if (isalpha(name[0]))
	    cerr << name  << " = " << a << " ";
	else
	    cerr << name << " ";
	_print(++it, args...);
}

typedef long long int int64;

const int INF = 1e9;

namespace slow {
  map<vector<int>, int> dp;

  vector<int> apply(const vector<int>&v, int a, int b) {
    vector<int> res;
    for (int i = 0; i < (int)v.size(); i++) {
      if (a <= i && i <= b) {
        res.push_back(v[i] + v[i + 1]);
        i++;
      } else {
        res.push_back(v[i]);
      }
    }
    return res;
  }

  int get_f(const vector<int>& v) {
    if (dp.count(v)) {
      return dp[v];
    }
    
    if (v.size() == 1) {
      return 0;
    }
    int ans = INF;
    for (int i = 0; i < (int)v.size(); i++) {
      for (int j = i + 1; j < (int)v.size(); j += 2) {
        vector<int> to = apply(v, i, j);
        int cur_ans = get_f(to) + 1;
        ans = min(ans, cur_ans);
      }
    }

    return dp[v] = ans;
  }
}

namespace fast {
  int get_log(int x) {
    assert(x >= 1);
    int res = 0;
    while (x > 1) {
      res++;
      x /= 2;
    }
    return res;
  }

  bool is_pow2(int x) {
    while (x % 2 == 0) {
      x /= 2;
    }
    return x == 1;
  }

  int get_op_cnt(int x) {
    int l = get_log(x);
    if (!is_pow2(x)) {
      l++;
    }
    return l;
  }

  int64 solve(vector<int> a_list) {
    int64 ans = 0;
    int op_cnt = 0;
    for (int a : a_list) {
      int need_op_cnt = get_op_cnt(a);
      if (need_op_cnt <= op_cnt) {
        if (is_pow2(a)) {
          op_cnt = need_op_cnt;
        } else {
          op_cnt = need_op_cnt - 1;
        }
      } else {
        ans += need_op_cnt - op_cnt;
        op_cnt = need_op_cnt;
      }
    }
    return ans;
  }
}

void test() {
  for (int i = 1; i <= 10; i++) {
    vector<int> v(i, 1);
    printf("size = %d ans = %d\n", i, slow::get_f(v));
  }
}

void submit() {
  int n;
  scanf("%d", &n);
  vector<int> a_list(n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a_list[i]);
  }
  int64 ans = fast::solve(a_list);
  printf("%lld\n", ans);
}

int main()
{
#ifdef LOCAL
	freopen ("input.txt", "r", stdin);
#endif

  submit();

	return 0;
}

```