#include "bits/stdc++.h"
using namespace std;


#define Seg_Max_N (1<<18) 

using Value = pair<long long int,int>;
const Value ini = (make_pair(1e18, 0));
struct segtree {
	int N;
	vector<Value>dat;

	segtree() {}
	segtree(int n) :dat(2 * Seg_Max_N) {
		N = 1;
		while (N < n) N *= 2;
		for (int i = 0; i < 2 * N - 1; i++) {
			dat[i] = ini;
			if (i >= N - 1) {
				dat[i].second = i - (N - 1);
			}
		}
	}
	Value connect(const Value&l, const Value&r) {
		
		return min(l, r);
	}
	// update k th element
	void update(int k, Value a) {
		k += N - 1;
		dat[k] = a;

		while (k > 0) {
			k = (k - 1) / 2;
			const Value al(dat[k * 2 + 1]);
			const Value ar(dat[k * 2 + 2]);
			dat[k] = connect(al, ar);
		}
	}
	// min [a, b)
	Value  query(int a, int b) { return query(a, b, 0, 0, N); }
	Value  query(int a, int b, int k, int l, int r) {
		if (r <= a or b <= l) return ini;
		if (a <= l and r <= b) return dat[k];
		const int m = (l + r) / 2;
		const Value al(query(a, b, k * 2 + 1, l, m));
		const Value ar(query(a, b, k * 2 + 2, m, r));
		return connect(al, ar);
	}
};
segtree seg;

vector<long long int>v;
int solve(int l, int r, long long int x) {
	if (l == r)return 0;
	Value av(seg.query(l, r));
	auto min_id = av.second;
	auto min_num =av.first;
	int ans=0;
	if (min_num >= x * 2) {
		ans= 1+solve(l, r, x * 2);
	}
	else if (min_num == x) {
		ans= solve(l, min_id ,x) + solve(min_id + 1, r,x);
	}else {
		int al = -1;

		int less2x_num = 0;
		vector<int>ts;
		for (int i = l; i < r; ++i) {
			if (v[i] >= 2*x) {
				if (al == -1)al = i;
			}
			else {
				less2x_num++;
				if (al == -1){}
				else {
					ts.push_back(0);
					ans += solve(al, i, 2 * x);
				}
				ts.push_back(1);
				al = -1;
			}
		}
		if (al == -1){}
		else {
			ts.push_back(0);
			ans += solve(al, r, 2 * x);
		}
		
		for (int aa = 0; aa < ts.size(); ++aa) {
			if (ts[aa] == 0) {
				aa++;
				if (aa == ts.size()) {
					ans++;
				}
				else {
					assert(ts[aa] == 1);
					ans++;
				}
			}
			else {
				aa++;
				ans++;
				if (aa == ts.size()) {
				}
				else {
					if (ts[aa] == 1) {
					}
					else {
						aa++;
						if (aa == ts.size()) {

						}
						else {
							assert(ts[aa] == 1);
						}
					}
				}
			}
		}
		return ans;
	}
	return ans;
}

int main() {
	int N; cin >> N;
	seg = segtree(N);

	v.resize(N);
	for (int i = 0; i < N; ++i) {
		cin >> v[i];
		seg.update(i, make_pair(v[i], i));
	}
	int ans = solve(0, N, 1);
	cout << ans << endl;

	return 0;
}
### 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 "bits/stdc++.h"
using namespace std;


#define Seg_Max_N (1<<18) 

using Value = pair<long long int,int>;
const Value ini = (make_pair(1e18, 0));
struct segtree {
	int N;
	vector<Value>dat;

	segtree() {}
	segtree(int n) :dat(2 * Seg_Max_N) {
		N = 1;
		while (N < n) N *= 2;
		for (int i = 0; i < 2 * N - 1; i++) {
			dat[i] = ini;
			if (i >= N - 1) {
				dat[i].second = i - (N - 1);
			}
		}
	}
	Value connect(const Value&l, const Value&r) {
		
		return min(l, r);
	}
	// update k th element
	void update(int k, Value a) {
		k += N - 1;
		dat[k] = a;

		while (k > 0) {
			k = (k - 1) / 2;
			const Value al(dat[k * 2 + 1]);
			const Value ar(dat[k * 2 + 2]);
			dat[k] = connect(al, ar);
		}
	}
	// min [a, b)
	Value  query(int a, int b) { return query(a, b, 0, 0, N); }
	Value  query(int a, int b, int k, int l, int r) {
		if (r <= a or b <= l) return ini;
		if (a <= l and r <= b) return dat[k];
		const int m = (l + r) / 2;
		const Value al(query(a, b, k * 2 + 1, l, m));
		const Value ar(query(a, b, k * 2 + 2, m, r));
		return connect(al, ar);
	}
};
segtree seg;

vector<long long int>v;
int solve(int l, int r, long long int x) {
	if (l == r)return 0;
	Value av(seg.query(l, r));
	auto min_id = av.second;
	auto min_num =av.first;
	int ans=0;
	if (min_num >= x * 2) {
		ans= 1+solve(l, r, x * 2);
	}
	else if (min_num == x) {
		ans= solve(l, min_id ,x) + solve(min_id + 1, r,x);
	}else {
		int al = -1;

		int less2x_num = 0;
		vector<int>ts;
		for (int i = l; i < r; ++i) {
			if (v[i] >= 2*x) {
				if (al == -1)al = i;
			}
			else {
				less2x_num++;
				if (al == -1){}
				else {
					ts.push_back(0);
					ans += solve(al, i, 2 * x);
				}
				ts.push_back(1);
				al = -1;
			}
		}
		if (al == -1){}
		else {
			ts.push_back(0);
			ans += solve(al, r, 2 * x);
		}
		
		for (int aa = 0; aa < ts.size(); ++aa) {
			if (ts[aa] == 0) {
				aa++;
				if (aa == ts.size()) {
					ans++;
				}
				else {
					assert(ts[aa] == 1);
					ans++;
				}
			}
			else {
				aa++;
				ans++;
				if (aa == ts.size()) {
				}
				else {
					if (ts[aa] == 1) {
					}
					else {
						aa++;
						if (aa == ts.size()) {

						}
						else {
							assert(ts[aa] == 1);
						}
					}
				}
			}
		}
		return ans;
	}
	return ans;
}

int main() {
	int N; cin >> N;
	seg = segtree(N);

	v.resize(N);
	for (int i = 0; i < N; ++i) {
		cin >> v[i];
		seg.update(i, make_pair(v[i], i));
	}
	int ans = solve(0, N, 1);
	cout << ans << endl;

	return 0;
}
```