#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef long long ll;
/*
x       0  1  2  3  4  5  6  7  8  9
bsr(x) -1  0  1  1  2  2  2  2  3  3
*/
int bsr(ll x){
	if(x==0) return -1;
	return 63 ^ __builtin_clzll(x);
}

ll dp[100010][2];
ll a[100010];
int main(){
	int N;
	cin>>N;
	rep(i,N) cin>>a[i];
	rep(i,N+1) rep(j,2) dp[i][j] = 1e18;
	rep(i,N){
		int k = bsr(a[i]);
		if(i==0){
			if((1LL<<k) == a[i]){
				dp[1][0]=k;
			}else{
				dp[1][1]=k+1;
			}
			continue;
		}
		int pk = bsr(a[i-1]);
		if((1LL<<k) == a[i]){
			rep(pt,2){
				chmin(dp[i+1][0],dp[i][pt]+k-min(k,pk+pt));
			}
		}else{
			rep(pt,2){
				rep(t,2){
					chmin(dp[i+1][1-t],dp[i][pt]+k+1-min(k+t,pk+pt));
				}
			}
		}
	}
	cout<<min(dp[N][0],dp[N][1])<<endl;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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 rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef long long ll;
/*
x       0  1  2  3  4  5  6  7  8  9
bsr(x) -1  0  1  1  2  2  2  2  3  3
*/
int bsr(ll x){
	if(x==0) return -1;
	return 63 ^ __builtin_clzll(x);
}

ll dp[100010][2];
ll a[100010];
int main(){
	int N;
	cin>>N;
	rep(i,N) cin>>a[i];
	rep(i,N+1) rep(j,2) dp[i][j] = 1e18;
	rep(i,N){
		int k = bsr(a[i]);
		if(i==0){
			if((1LL<<k) == a[i]){
				dp[1][0]=k;
			}else{
				dp[1][1]=k+1;
			}
			continue;
		}
		int pk = bsr(a[i-1]);
		if((1LL<<k) == a[i]){
			rep(pt,2){
				chmin(dp[i+1][0],dp[i][pt]+k-min(k,pk+pt));
			}
		}else{
			rep(pt,2){
				rep(t,2){
					chmin(dp[i+1][1-t],dp[i][pt]+k+1-min(k+t,pk+pt));
				}
			}
		}
	}
	cout<<min(dp[N][0],dp[N][1])<<endl;
}

```