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

#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); i--)
#define ITER(it, a) for(typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a, value, sizeof(a))

#define SZ(a) (int) a.size()
#define ALL(a) a.begin(),a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const LL INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;

const int MAX = 100100;

int A[MAX];

vector<PII> B[MAX];
int DP[MAX][2];

int getLen(int x)
{
	int a = 1;
	int res = 0;
	while(a < x)
	{
		a *= 2;
		res++;
	}

	return res;
}

void add(int ind, int x)
{
	int len = getLen(x);
	if (x == (1<<len))
	{
		B[ind].PB(MP(len, len));
		return;
	}

//	cout<<x<<": "<<len<<endl;

	B[ind].PB(MP(len - 1, len));
	B[ind].PB(MP(len, len - 1));
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//ios::sync_with_stdio(false); cin.tie(0);

	int n;
	scanf("%d", &n);
	FOR (i, 0, n)
	{
		int x;
		scanf("%d", &x);

		add(i, x);
	}

	FOR (i, 0, n)
	{
		DP[i][0] = DP[i][1] = INF;
	}

	DP[0][0] = max(B[0][0].first, B[0][0].second);
	if (SZ(B[0]) > 1)
	{
		DP[0][1] = DP[0][0];
	}

	FOR (i, 0, n)
	{
		FOR (j, 0, SZ(B[i]))
		{
			FOR (k, 0, SZ(B[i+1]))
			{
				DP[i+1][k] = min(DP[i+1][k], DP[i][j] + max(B[i+1][k].first, B[i+1][k].second) - min(B[i][j].second, B[i+1][k].first));
			}
		}
	}

/*	FOR (i, 0, n)
	{
		FOR (j, 0, SZ(B[i]))
		{
			cout<<DP[i][j]<<' ';
		}
		cout<<endl;
	}
	cout<<endl;*/

	int res = INF;
	FOR (i, 0, SZ(B[n-1]))
	{
		res = min(res, DP[n-1][i]);
	}

	cout<<res<<endl;
}

### Prompt

Please create a solution in CPP 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 FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); i--)
#define ITER(it, a) for(typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a, value, sizeof(a))

#define SZ(a) (int) a.size()
#define ALL(a) a.begin(),a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const LL INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;

const int MAX = 100100;

int A[MAX];

vector<PII> B[MAX];
int DP[MAX][2];

int getLen(int x)
{
	int a = 1;
	int res = 0;
	while(a < x)
	{
		a *= 2;
		res++;
	}

	return res;
}

void add(int ind, int x)
{
	int len = getLen(x);
	if (x == (1<<len))
	{
		B[ind].PB(MP(len, len));
		return;
	}

//	cout<<x<<": "<<len<<endl;

	B[ind].PB(MP(len - 1, len));
	B[ind].PB(MP(len, len - 1));
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//ios::sync_with_stdio(false); cin.tie(0);

	int n;
	scanf("%d", &n);
	FOR (i, 0, n)
	{
		int x;
		scanf("%d", &x);

		add(i, x);
	}

	FOR (i, 0, n)
	{
		DP[i][0] = DP[i][1] = INF;
	}

	DP[0][0] = max(B[0][0].first, B[0][0].second);
	if (SZ(B[0]) > 1)
	{
		DP[0][1] = DP[0][0];
	}

	FOR (i, 0, n)
	{
		FOR (j, 0, SZ(B[i]))
		{
			FOR (k, 0, SZ(B[i+1]))
			{
				DP[i+1][k] = min(DP[i+1][k], DP[i][j] + max(B[i+1][k].first, B[i+1][k].second) - min(B[i][j].second, B[i+1][k].first));
			}
		}
	}

/*	FOR (i, 0, n)
	{
		FOR (j, 0, SZ(B[i]))
		{
			cout<<DP[i][j]<<' ';
		}
		cout<<endl;
	}
	cout<<endl;*/

	int res = INF;
	FOR (i, 0, SZ(B[n-1]))
	{
		res = min(res, DP[n-1][i]);
	}

	cout<<res<<endl;
}

```