#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")  
using namespace std;

#define mp make_pair  
#define Fi first  
#define Se second  
#define pb(x) push_back(x)  
#define szz(x) ((int)(x).size()) 
#define all(x) (x).begin(), (x).end()  
#define ldb ldouble  

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 17;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;

class Node {
public:
	int mn, v;
	Node() {
		*this = Node(0, 0);
	}
	Node(int mn, int v) : mn(mn), v(v) {}
};
Node indt[600000];
void propagate(int n) {
	int v = indt[n].v;
	indt[2 * n].mn += v;
	indt[2 * n].v += v;
	indt[2 * n + 1].mn += v;
	indt[2 * n + 1].v += v;
	indt[n].v = 0;
}
void update(int st, int en, int S, int E, int n, int v) {
	if (en < S || E < st) return;
	if (st <= S && E <= en) {
		indt[n].mn += v;
		indt[n].v += v;
		return;
	}
	propagate(n);
	int M = (S + E) / 2;
	update(st, en, S, M, 2 * n, v);
	update(st, en, M + 1, E, 2 * n + 1, v);
	indt[n].mn = min(indt[2 * n].mn, indt[2 * n + 1].mn);
}
int getmn(int st, int en, int S, int E, int n) {
	if (en < S || E < st) return INF;
	if (st <= S && E <= en) return indt[n].mn;
	propagate(n);

	int M = (S + E) / 2;
	return min(getmn(st, en, S, M, 2 * n), getmn(st, en, M + 1, E, 2 * n + 1));
}

ll ans = 0;
void dodo(int st, int en) {
	if (st > en) return;
	int mn = getmn(st, en, 1, IT_MAX, 1);
	ans += mn;
	update(st, en, 1, IT_MAX, 1, -mn);

	while (st <= en) {
		int s = st, e = en, m, r = en + 1;
		while (s <= e) {
			m = (s + e) / 2;
			if (getmn(s, m, 1, IT_MAX, 1) == 0) {
				r = m;
				e = m - 1;
			}
			else s = m + 1;
		}
		dodo(st, r - 1);
		st = r + 1;
	}
}

pii in[100050];
bool chk[100050];
int main() {
	int N, i, j, k;
	scanf("%d", &N);
	for (i = 1; i <= N; i++) {
		int t;
		scanf("%d", &t);
		for (j = 0, k = 1; t >= (ll)2*k; j++, k *= 2);
		in[i].second = j;
		if (k == t) in[i].first = j;
		else in[i].first = j + 1;
	}
	for (i = 1; i <= N; i++) {
		chk[i] = true;
		if (in[i].first == in[i].second) chk[i] = false;
		if (i != 1 && in[i] < in[i - 1]) chk[i] = false;
		if (i != N && in[i] < in[i + 1]) chk[i] = false;
	}

	ll c = 0;
	for (i = 1; i <= N; i++) {
		if (!chk[i]) continue;
		c++;
		if (i == N || !chk[i + 1]) {
			ans += (c + 1) / 2;
			c = 0;
		}
	}

	for (i = 1; i <= N; i++) update(i, i, 1, IT_MAX, 1, in[i].second);
	dodo(1, N);
	return !printf("%lld\n", ans);
}
### 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 <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")  
using namespace std;

#define mp make_pair  
#define Fi first  
#define Se second  
#define pb(x) push_back(x)  
#define szz(x) ((int)(x).size()) 
#define all(x) (x).begin(), (x).end()  
#define ldb ldouble  

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 17;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;

class Node {
public:
	int mn, v;
	Node() {
		*this = Node(0, 0);
	}
	Node(int mn, int v) : mn(mn), v(v) {}
};
Node indt[600000];
void propagate(int n) {
	int v = indt[n].v;
	indt[2 * n].mn += v;
	indt[2 * n].v += v;
	indt[2 * n + 1].mn += v;
	indt[2 * n + 1].v += v;
	indt[n].v = 0;
}
void update(int st, int en, int S, int E, int n, int v) {
	if (en < S || E < st) return;
	if (st <= S && E <= en) {
		indt[n].mn += v;
		indt[n].v += v;
		return;
	}
	propagate(n);
	int M = (S + E) / 2;
	update(st, en, S, M, 2 * n, v);
	update(st, en, M + 1, E, 2 * n + 1, v);
	indt[n].mn = min(indt[2 * n].mn, indt[2 * n + 1].mn);
}
int getmn(int st, int en, int S, int E, int n) {
	if (en < S || E < st) return INF;
	if (st <= S && E <= en) return indt[n].mn;
	propagate(n);

	int M = (S + E) / 2;
	return min(getmn(st, en, S, M, 2 * n), getmn(st, en, M + 1, E, 2 * n + 1));
}

ll ans = 0;
void dodo(int st, int en) {
	if (st > en) return;
	int mn = getmn(st, en, 1, IT_MAX, 1);
	ans += mn;
	update(st, en, 1, IT_MAX, 1, -mn);

	while (st <= en) {
		int s = st, e = en, m, r = en + 1;
		while (s <= e) {
			m = (s + e) / 2;
			if (getmn(s, m, 1, IT_MAX, 1) == 0) {
				r = m;
				e = m - 1;
			}
			else s = m + 1;
		}
		dodo(st, r - 1);
		st = r + 1;
	}
}

pii in[100050];
bool chk[100050];
int main() {
	int N, i, j, k;
	scanf("%d", &N);
	for (i = 1; i <= N; i++) {
		int t;
		scanf("%d", &t);
		for (j = 0, k = 1; t >= (ll)2*k; j++, k *= 2);
		in[i].second = j;
		if (k == t) in[i].first = j;
		else in[i].first = j + 1;
	}
	for (i = 1; i <= N; i++) {
		chk[i] = true;
		if (in[i].first == in[i].second) chk[i] = false;
		if (i != 1 && in[i] < in[i - 1]) chk[i] = false;
		if (i != N && in[i] < in[i + 1]) chk[i] = false;
	}

	ll c = 0;
	for (i = 1; i <= N; i++) {
		if (!chk[i]) continue;
		c++;
		if (i == N || !chk[i + 1]) {
			ans += (c + 1) / 2;
			c = 0;
		}
	}

	for (i = 1; i <= N; i++) update(i, i, 1, IT_MAX, 1, in[i].second);
	dodo(1, N);
	return !printf("%lld\n", ans);
}
```