#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
typedef pair<int, int> pii;
 
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define REP(i, a, b)  for(int i = (a), i##end = (b); i < i##end; ++i)
#define DREP(i, a, b) for(int i=(a-1), i##end = (b); i >=i##end; --i)
 
template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
 
const int maxl = 35;
const int maxn = 100000 + 5;
const int oo = 0x3f3f3f3f;
 
template<typename T> T read() {
    T n(0), f(1);
    char ch = getchar();
    for( ;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for( ; isdigit(ch); ch = getchar()) n = n * 10 + ch - 48; 
    return n * f;
}

int n;
int a[maxn];
int dp[2][maxl];

int main() {
#ifdef Wearry
    freopen("data.txt", "r", stdin);
    freopen("ans.txt", "w", stdout);
#endif

    n = read<int>();
    for(int i = 1; i <= n; ++i) { a[i] = read<int>(); }

    int cur = 0;
    memset(dp[cur], oo, sizeof dp[cur]);

    dp[cur][0] = 0;
    for(int i = 1; i <= n; ++i) {
        int bit = 0, x = 1;
        while(x < a[i]) x <<= 1, ++ bit;

        cur ^= 1;
        memset(dp[cur], oo, sizeof dp[cur]);

        for(int j = 0; j <= bit; ++j) if(dp[cur^1][j] < oo) {
            int delta = bit - j; 

            if(delta > 0 || x == a[i]) 
                chkmin(dp[cur][bit], dp[cur^1][j] + delta);
            else if(j > 0) 
                chkmin(dp[cur][bit-1], dp[cur^1][j] + delta);
        }
        for(int j = bit; j > 0; --j) chkmin(dp[cur][j-1], dp[cur][j]);
    }
    printf("%d\n", dp[cur][0]);

    return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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;
 
typedef long long LL;
typedef pair<int, int> pii;
 
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define REP(i, a, b)  for(int i = (a), i##end = (b); i < i##end; ++i)
#define DREP(i, a, b) for(int i=(a-1), i##end = (b); i >=i##end; --i)
 
template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
 
const int maxl = 35;
const int maxn = 100000 + 5;
const int oo = 0x3f3f3f3f;
 
template<typename T> T read() {
    T n(0), f(1);
    char ch = getchar();
    for( ;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for( ; isdigit(ch); ch = getchar()) n = n * 10 + ch - 48; 
    return n * f;
}

int n;
int a[maxn];
int dp[2][maxl];

int main() {
#ifdef Wearry
    freopen("data.txt", "r", stdin);
    freopen("ans.txt", "w", stdout);
#endif

    n = read<int>();
    for(int i = 1; i <= n; ++i) { a[i] = read<int>(); }

    int cur = 0;
    memset(dp[cur], oo, sizeof dp[cur]);

    dp[cur][0] = 0;
    for(int i = 1; i <= n; ++i) {
        int bit = 0, x = 1;
        while(x < a[i]) x <<= 1, ++ bit;

        cur ^= 1;
        memset(dp[cur], oo, sizeof dp[cur]);

        for(int j = 0; j <= bit; ++j) if(dp[cur^1][j] < oo) {
            int delta = bit - j; 

            if(delta > 0 || x == a[i]) 
                chkmin(dp[cur][bit], dp[cur^1][j] + delta);
            else if(j > 0) 
                chkmin(dp[cur][bit-1], dp[cur^1][j] + delta);
        }
        for(int j = bit; j > 0; --j) chkmin(dp[cur][j-1], dp[cur][j]);
    }
    printf("%d\n", dp[cur][0]);

    return 0;
}

```