#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#ifdef _DEBUG_
	#define debug(...) printf(__VA_ARGS__)
#else
	#define debug(...) (void)0
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

const int MAXN = 1e5 + 100;
int a[MAXN];
int q[MAXN * 2];

int LC(int x) { return 2 * x + 1; }
int RC(int x) { return 2 * x + 2; }
int st[MAXN * 8];
void build(int l, int r, int id) {
	if (l == r) {
		st[id] = l;
		return;
	}
	int m = (l + r) / 2;
	build(l, m, LC(id));
	build(m + 1, r, RC(id));
	if (q[st[LC(id)]] < q[st[RC(id)]])
		st[id] = st[LC(id)];
	else
		st[id] = st[RC(id)];
	//st[id] = min(st[LC(id)], st[RC(id)]);
}
int query(int l, int r, int id, int ql, int qr) {
	if (ql <= l && qr >= r)
		return st[id];
	int m = (l + r) / 2;
	int res = ql;
	if (ql <= m) {
		int t = query(l, m, LC(id), ql, qr);
		if (q[t] < q[res])
			res = t;
	}
	if (qr > m) {
		int t = query(m + 1, r, RC(id), ql, qr);
		if (q[t] < q[res])
			res = t;
	}
	return res;
}

int N;
int go(int l, int r, int sub) {
	debug("go(%d, %d, %d)\n", l, r, sub);
	while (l <= r && q[l] == sub) l++;
	while (l <= r && q[r] == sub) r--;
	if (l > r) return 0;
	int id = query(0, 2 * N - 1, 0, l, r);
	debug("id: %d\n", id);
	int ansl = go(l, id - 1, q[id]);
	int ansr = go(id + 1, r, q[id]);
	return ansl + ansr + q[id] - sub;
}

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%d", &a[i]);
	for (int i = 0; i < N; i++) {
		int t = 0;
		bool need = false;
		while (a[i] > 1) {
			t++;
			if (a[i] % 2 != 0) need = true;
			a[i] /= 2;
		}
		if (need) q[2 * i] = t + 1, q[2 * i + 1] = t;
		else q[2 * i] = q[2 * i + 1] = t;
	}
	swap(q[0], q[1]);
	for (int i = 1; i < N - 1; i++) {
		if (q[2 * i - 1] < q[2 * i + 2])
			swap(q[2 * i], q[2 * i + 1]);
	}
	build(0, 2 * N - 1, 0);
//	for (int i = 0; i < 10; i++) debug("q[%d]: %d\n", i, q[i]);
//	for (int i = 0; i < 10; i++) debug("st[%d]: %d\n", i, st[i]);
//	debug("test - %d\n", query(0, 2 * N - 1, 0, 1, 2));
//	return 0;//
	int res = go(0, 2 * N - 1, 0);
	cout << res << endl;
	return 0;
}

### 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 <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#ifdef _DEBUG_
	#define debug(...) printf(__VA_ARGS__)
#else
	#define debug(...) (void)0
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

const int MAXN = 1e5 + 100;
int a[MAXN];
int q[MAXN * 2];

int LC(int x) { return 2 * x + 1; }
int RC(int x) { return 2 * x + 2; }
int st[MAXN * 8];
void build(int l, int r, int id) {
	if (l == r) {
		st[id] = l;
		return;
	}
	int m = (l + r) / 2;
	build(l, m, LC(id));
	build(m + 1, r, RC(id));
	if (q[st[LC(id)]] < q[st[RC(id)]])
		st[id] = st[LC(id)];
	else
		st[id] = st[RC(id)];
	//st[id] = min(st[LC(id)], st[RC(id)]);
}
int query(int l, int r, int id, int ql, int qr) {
	if (ql <= l && qr >= r)
		return st[id];
	int m = (l + r) / 2;
	int res = ql;
	if (ql <= m) {
		int t = query(l, m, LC(id), ql, qr);
		if (q[t] < q[res])
			res = t;
	}
	if (qr > m) {
		int t = query(m + 1, r, RC(id), ql, qr);
		if (q[t] < q[res])
			res = t;
	}
	return res;
}

int N;
int go(int l, int r, int sub) {
	debug("go(%d, %d, %d)\n", l, r, sub);
	while (l <= r && q[l] == sub) l++;
	while (l <= r && q[r] == sub) r--;
	if (l > r) return 0;
	int id = query(0, 2 * N - 1, 0, l, r);
	debug("id: %d\n", id);
	int ansl = go(l, id - 1, q[id]);
	int ansr = go(id + 1, r, q[id]);
	return ansl + ansr + q[id] - sub;
}

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%d", &a[i]);
	for (int i = 0; i < N; i++) {
		int t = 0;
		bool need = false;
		while (a[i] > 1) {
			t++;
			if (a[i] % 2 != 0) need = true;
			a[i] /= 2;
		}
		if (need) q[2 * i] = t + 1, q[2 * i + 1] = t;
		else q[2 * i] = q[2 * i + 1] = t;
	}
	swap(q[0], q[1]);
	for (int i = 1; i < N - 1; i++) {
		if (q[2 * i - 1] < q[2 * i + 2])
			swap(q[2 * i], q[2 * i + 1]);
	}
	build(0, 2 * N - 1, 0);
//	for (int i = 0; i < 10; i++) debug("q[%d]: %d\n", i, q[i]);
//	for (int i = 0; i < 10; i++) debug("st[%d]: %d\n", i, st[i]);
//	debug("test - %d\n", query(0, 2 * N - 1, 0, 1, 2));
//	return 0;//
	int res = go(0, 2 * N - 1, 0);
	cout << res << endl;
	return 0;
}

```