#include <bits/stdc++.h>
 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define li long long
#define itn int
 
using namespace std;
 
inline int nxt(){
	int n;
	scanf("%d", &n);
	return n;
}

template <typename T>
ostream& operator <<(ostream& ostr, const vector<T>& a) {
	ostr << "(";
	for (size_t i = 0; i < a.size(); ++i) {
		if (i) {
			ostr << ", ";
		}
		ostr << a[i];
	}
	ostr << ")";
	return ostr;
}

int f(int x) {
	if (x & 1) {
		return 1 << (31 - __builtin_clz(x));
	} else {
		return x >> 1;
	}
}

int get(vector<int> a) {
	int n = a.size();
	vector<int> b(n);
	vector<int> bad;
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		if (__builtin_popcount(a[i]) > 1) {
			bad.push_back(i);
			b[i] = 1;
		}
		b[i] += 31 - __builtin_clz(a[i]);
	}
	ans += accumulate(all(b), 0);
	for (int i = 0; i < n - 1; ++i) {
		ans -= min(b[i], b[i + 1]);
	}

	vector<int> really_bad;
	for (int idx : bad) {
		int cnt_near_greater = 0;
		if (idx > 0 && b[idx - 1] >= b[idx]) {
			++cnt_near_greater;
		}
		if (idx < n - 1 && b[idx + 1] >= b[idx]) {
			++cnt_near_greater;
		}
		if (cnt_near_greater == 2) {
			really_bad.push_back(idx);
		}
	}

	for (int i = 0; i < (int)really_bad.size();) {
		ans += 1;
		if (i == (int)really_bad.size() - 1) {
			break;
		}
		if (really_bad[i] + 1 == really_bad[i + 1]) {
			i += 2;
		} else {
			i += 1;
		}
	}

	return ans;
}

int main() {
	int n = nxt();
	vector<int> a(n);
	for (itn i = 0; i < n; ++i) {
		a[i] = nxt();
	}

	int ans = 0;
	vector<int> b;
	for (int x : a) {
		if (x == 1) {
			ans += get(b);
			b.clear();
		} else {
			b.push_back(x);
		}
	}
	ans += get(b);

	printf("%d\n", ans);

	return 0;
}
### Prompt

Create a solution in Cpp for 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 <bits/stdc++.h>
 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define li long long
#define itn int
 
using namespace std;
 
inline int nxt(){
	int n;
	scanf("%d", &n);
	return n;
}

template <typename T>
ostream& operator <<(ostream& ostr, const vector<T>& a) {
	ostr << "(";
	for (size_t i = 0; i < a.size(); ++i) {
		if (i) {
			ostr << ", ";
		}
		ostr << a[i];
	}
	ostr << ")";
	return ostr;
}

int f(int x) {
	if (x & 1) {
		return 1 << (31 - __builtin_clz(x));
	} else {
		return x >> 1;
	}
}

int get(vector<int> a) {
	int n = a.size();
	vector<int> b(n);
	vector<int> bad;
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		if (__builtin_popcount(a[i]) > 1) {
			bad.push_back(i);
			b[i] = 1;
		}
		b[i] += 31 - __builtin_clz(a[i]);
	}
	ans += accumulate(all(b), 0);
	for (int i = 0; i < n - 1; ++i) {
		ans -= min(b[i], b[i + 1]);
	}

	vector<int> really_bad;
	for (int idx : bad) {
		int cnt_near_greater = 0;
		if (idx > 0 && b[idx - 1] >= b[idx]) {
			++cnt_near_greater;
		}
		if (idx < n - 1 && b[idx + 1] >= b[idx]) {
			++cnt_near_greater;
		}
		if (cnt_near_greater == 2) {
			really_bad.push_back(idx);
		}
	}

	for (int i = 0; i < (int)really_bad.size();) {
		ans += 1;
		if (i == (int)really_bad.size() - 1) {
			break;
		}
		if (really_bad[i] + 1 == really_bad[i + 1]) {
			i += 2;
		} else {
			i += 1;
		}
	}

	return ans;
}

int main() {
	int n = nxt();
	vector<int> a(n);
	for (itn i = 0; i < n; ++i) {
		a[i] = nxt();
	}

	int ans = 0;
	vector<int> b;
	for (int x : a) {
		if (x == 1) {
			ans += get(b);
			b.clear();
		} else {
			b.push_back(x);
		}
	}
	ans += get(b);

	printf("%d\n", ans);

	return 0;
}
```