#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

#define fi first
#define se second

int n;
int a[125252];
pii p[125252];
pii dp[125252][2];

void pma(pii &a, pii b){
  if(a.first > b.first){
    a = b;
  }else if(a.first == b.first && a.second < b.second){
    a = b;
  }
}

int main(){
  scanf("%d",&n);
  REP(i,n)scanf("%d",a+i);
  REP(i,n){
    int x = a[i];
    int y=0, z=0;
    if(__builtin_popcount(x)==1){
      y = 1;
    }
    while(x>1){
      z++;
      x = (x+1)/2;
    }
    p[i] = pii(y,z);
  }
  pii PO = pii(1e9, -1e9);
  REP(i,n+1)dp[i][0] = dp[i][1] = PO;
  dp[0][0] = dp[0][1] = pii(0,0);
  REP(i,n){
    if(p[i].first == 1){
      // pow 2
      pii nxt = PO;
      pii x = dp[i][0];
      pma(nxt, pii(x.fi + max(0,p[i].se-x.se), p[i].se));
      x = dp[i][1];
      pma(nxt, pii(x.fi + max(0,p[i].se-x.se), p[i].se));
      dp[i+1][0] = dp[i+1][1] = nxt;
    }else{
      // left connect (0)
      {
        pii nxt = PO;
        pii x = dp[i][0];
        pma(nxt, pii(x.fi + max(0,p[i].se-x.se), max(0,p[i].se-1)));
        x = dp[i][1];
        pma(nxt, pii(x.fi + max(0,p[i].se-x.se), max(0,p[i].se-1)));
        dp[i+1][0] = nxt;
      }
      // right connect (1)
      {
        pii nxt = PO;
        pii x = dp[i][0];
        pma(nxt, pii(x.fi + max(0,(p[i].se-1)-x.se) + 1, p[i].se));
        x = dp[i][1];
        pma(nxt, pii(x.fi + max(0,(p[i].se-1)-x.se) + 1, p[i].se));
        dp[i+1][1] = nxt;
      }
    }
  }
  // REP(i,n+1){
  //   printf("(%4d,%4d) (%4d,%4d)\n", dp[i][0].fi, dp[i][0].se, dp[i][1].fi, dp[i][1].se);
  // }
  int ans = min(dp[n][0].fi, dp[n][1].fi);
  printf("%d\n",ans);
  return 0;
}

### Prompt

Your task is to create 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>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

#define fi first
#define se second

int n;
int a[125252];
pii p[125252];
pii dp[125252][2];

void pma(pii &a, pii b){
  if(a.first > b.first){
    a = b;
  }else if(a.first == b.first && a.second < b.second){
    a = b;
  }
}

int main(){
  scanf("%d",&n);
  REP(i,n)scanf("%d",a+i);
  REP(i,n){
    int x = a[i];
    int y=0, z=0;
    if(__builtin_popcount(x)==1){
      y = 1;
    }
    while(x>1){
      z++;
      x = (x+1)/2;
    }
    p[i] = pii(y,z);
  }
  pii PO = pii(1e9, -1e9);
  REP(i,n+1)dp[i][0] = dp[i][1] = PO;
  dp[0][0] = dp[0][1] = pii(0,0);
  REP(i,n){
    if(p[i].first == 1){
      // pow 2
      pii nxt = PO;
      pii x = dp[i][0];
      pma(nxt, pii(x.fi + max(0,p[i].se-x.se), p[i].se));
      x = dp[i][1];
      pma(nxt, pii(x.fi + max(0,p[i].se-x.se), p[i].se));
      dp[i+1][0] = dp[i+1][1] = nxt;
    }else{
      // left connect (0)
      {
        pii nxt = PO;
        pii x = dp[i][0];
        pma(nxt, pii(x.fi + max(0,p[i].se-x.se), max(0,p[i].se-1)));
        x = dp[i][1];
        pma(nxt, pii(x.fi + max(0,p[i].se-x.se), max(0,p[i].se-1)));
        dp[i+1][0] = nxt;
      }
      // right connect (1)
      {
        pii nxt = PO;
        pii x = dp[i][0];
        pma(nxt, pii(x.fi + max(0,(p[i].se-1)-x.se) + 1, p[i].se));
        x = dp[i][1];
        pma(nxt, pii(x.fi + max(0,(p[i].se-1)-x.se) + 1, p[i].se));
        dp[i+1][1] = nxt;
      }
    }
  }
  // REP(i,n+1){
  //   printf("(%4d,%4d) (%4d,%4d)\n", dp[i][0].fi, dp[i][0].se, dp[i][1].fi, dp[i][1].se);
  // }
  int ans = min(dp[n][0].fi, dp[n][1].fi);
  printf("%d\n",ans);
  return 0;
}

```