#include <bits/stdc++.h>

using namespace std;
using namespace std::chrono;

#define rep(i,a,b) for(int i = a;i<(b);++i)
#define trav(a,v) for(auto& a : v)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;

const ll big = 1000000007ll;
const ll big2 = 1000000009ll;
ll n,m,k,q,w,h;

ll DP[100001][2] = {0};

vector<ll> X;
vector<ll> B;

ll dp(ll i, ll a){
    if(i == n)return 0;
    if(DP[i][a] != -1)return DP[i][a];
    ll a1 = min(X[i-1]-a*B[i-1],X[i]) + dp(i+1,1);
    ll a2 = min(X[i-1]-a*B[i-1],X[i]-B[i]) + dp(i+1,0);
    DP[i][a] = max(a1,a2);
    return DP[i][a];
}

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("autput.txt","w",stdout);
    ll a,b,c,d;
    cin >> n;
    ll sx = 0;
    for(ll c1 = 0; c1 < n; c1++){
        cin >> a;
        ll t = 1;
        b = 0;
        while(t < a){
            t *= 2;
            b++;
        }
        X.push_back(b);
        B.push_back(t != a);
        DP[c1][0] = -1;
        DP[c1][1] = -1;
        sx += X[c1];
    }
    ll ans = sx-max(dp(1,0),dp(1,1));
    cout << ans << "\n";
    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 <bits/stdc++.h>

using namespace std;
using namespace std::chrono;

#define rep(i,a,b) for(int i = a;i<(b);++i)
#define trav(a,v) for(auto& a : v)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;

const ll big = 1000000007ll;
const ll big2 = 1000000009ll;
ll n,m,k,q,w,h;

ll DP[100001][2] = {0};

vector<ll> X;
vector<ll> B;

ll dp(ll i, ll a){
    if(i == n)return 0;
    if(DP[i][a] != -1)return DP[i][a];
    ll a1 = min(X[i-1]-a*B[i-1],X[i]) + dp(i+1,1);
    ll a2 = min(X[i-1]-a*B[i-1],X[i]-B[i]) + dp(i+1,0);
    DP[i][a] = max(a1,a2);
    return DP[i][a];
}

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("autput.txt","w",stdout);
    ll a,b,c,d;
    cin >> n;
    ll sx = 0;
    for(ll c1 = 0; c1 < n; c1++){
        cin >> a;
        ll t = 1;
        b = 0;
        while(t < a){
            t *= 2;
            b++;
        }
        X.push_back(b);
        B.push_back(t != a);
        DP[c1][0] = -1;
        DP[c1][1] = -1;
        sx += X[c1];
    }
    ll ans = sx-max(dp(1,0),dp(1,1));
    cout << ans << "\n";
    return 0;
}

```