#include <bits/stdc++.h>

#ifndef LOCAL
#define cerr dolor_sit_amet
#endif

#define mp make_pair
#define sz(x) ((int)((x).size()))
#define X first
#define Y second

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < int , int > ipair;
typedef pair < ll , ll > lpair;
const int IINF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;
const double DINF = numeric_limits<double>::infinity();
const int MOD = 1000000007;
const double EPS = 1e-9;
const int DX[] = { 1,  0, -1,  0,  1, -1,  1, -1};
const int DY[] = { 0,  1,  0, -1,  1, -1, -1,  1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll sqr(ll x) { return x*x; } ll sqr(int x) { return (ll)x*x; }
double sqr(double x) { return x*x; } ld sqr(ld x) { return x*x; }
mt19937 mmtw(960172);
ll rnd(ll x, ll y) { static uniform_int_distribution<ll> d; return d(mmtw) % (y - x + 1) + x; }

// ========================================================================= //

const int N = 100179;

int n;
int a[N];
bool f[N];

int main() {
    ios::sync_with_stdio(false);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        f[i] = (x & (x-1));
        int y = 1;
        while (true) {
            if (y * 2 > x)
                break;
            y *= 2;
            ++a[i];
        }
    }

    int ans = 0;
    while (true) {
        int pans = ans;
        for (int i = 0; i < n; ++i) {
            if (f[i] || a[i]) {
                ++ans;
                int j = i;
                while (j < n - 1 && (i == j || a[j]) && (a[j+1] || f[j+1]))
                    ++j;
                if (a[i])
                    --a[i];
                else
                    f[i] = 0;
                if (i != j) {
                    if (a[j])
                        --a[j];
                    else
                        f[j] = 0;
                }
                for (int k = i+1; k < j; ++k)
                    --a[k];
                i = j;
            }
        }
        if (pans == ans)
            break;
    }
    cout << ans << "\n";

    return 0;
}

### Prompt

Please formulate a Cpp solution 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>

#ifndef LOCAL
#define cerr dolor_sit_amet
#endif

#define mp make_pair
#define sz(x) ((int)((x).size()))
#define X first
#define Y second

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < int , int > ipair;
typedef pair < ll , ll > lpair;
const int IINF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;
const double DINF = numeric_limits<double>::infinity();
const int MOD = 1000000007;
const double EPS = 1e-9;
const int DX[] = { 1,  0, -1,  0,  1, -1,  1, -1};
const int DY[] = { 0,  1,  0, -1,  1, -1, -1,  1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll sqr(ll x) { return x*x; } ll sqr(int x) { return (ll)x*x; }
double sqr(double x) { return x*x; } ld sqr(ld x) { return x*x; }
mt19937 mmtw(960172);
ll rnd(ll x, ll y) { static uniform_int_distribution<ll> d; return d(mmtw) % (y - x + 1) + x; }

// ========================================================================= //

const int N = 100179;

int n;
int a[N];
bool f[N];

int main() {
    ios::sync_with_stdio(false);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        f[i] = (x & (x-1));
        int y = 1;
        while (true) {
            if (y * 2 > x)
                break;
            y *= 2;
            ++a[i];
        }
    }

    int ans = 0;
    while (true) {
        int pans = ans;
        for (int i = 0; i < n; ++i) {
            if (f[i] || a[i]) {
                ++ans;
                int j = i;
                while (j < n - 1 && (i == j || a[j]) && (a[j+1] || f[j+1]))
                    ++j;
                if (a[i])
                    --a[i];
                else
                    f[i] = 0;
                if (i != j) {
                    if (a[j])
                        --a[j];
                    else
                        f[j] = 0;
                }
                for (int k = i+1; k < j; ++k)
                    --a[k];
                i = j;
            }
        }
        if (pans == ans)
            break;
    }
    cout << ans << "\n";

    return 0;
}

```