#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

int n, p[100010];
int a[100010];

void solve(){
	scanf("%d", &n);
	for(int i=1;i<=n;i++) scanf("%d", p+i);
	for(int i=1;i<=n;i++) a[i] = 1;
	int ans = 0;
	for(int i=1;i<=n;i++) {
		while(a[i] != p[i]) {
			++ans;
			if(a[i] * 2 <= p[i]) a[i] *= 2;
			else a[i] = p[i];
			for(int j=i+1;j<=n;j++) {
				if(a[j] * 2 <= p[j]) a[j] *= 2;
				else { a[j] = p[j]; break; }
			}
		}
	}
	printf("%d\n", ans);
}

int main(){
	int Tc = 1; //scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		// printf("Case #%d: ", tc);
		solve();
	}
	return 0;
}
### Prompt

In Cpp, your task is to solve 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 <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

int n, p[100010];
int a[100010];

void solve(){
	scanf("%d", &n);
	for(int i=1;i<=n;i++) scanf("%d", p+i);
	for(int i=1;i<=n;i++) a[i] = 1;
	int ans = 0;
	for(int i=1;i<=n;i++) {
		while(a[i] != p[i]) {
			++ans;
			if(a[i] * 2 <= p[i]) a[i] *= 2;
			else a[i] = p[i];
			for(int j=i+1;j<=n;j++) {
				if(a[j] * 2 <= p[j]) a[j] *= 2;
				else { a[j] = p[j]; break; }
			}
		}
	}
	printf("%d\n", ans);
}

int main(){
	int Tc = 1; //scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		// printf("Case #%d: ", tc);
		solve();
	}
	return 0;
}
```