#include <bits/stdc++.h>
using namespace std;
template <class T>
void _R(T &x) {
  cin >> x;
}
void _R(int &x) { scanf("%d", &x); }
void _R(long long &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template <class T, class... U>
void R(T &head, U &...tail) {
  _R(head);
  R(tail...);
}
template <class T>
void _W(const T &x) {
  cout << x;
}
void _W(const int &x) { printf("%d", x); }
void _W(const long long &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T, class U>
void _W(const pair<T, U> &x) {
  _W(x.first);
  putchar(' ');
  _W(x.second);
}
template <class T>
void _W(const vector<T> &x) {
  for (auto i = x.begin(); i != x.end(); _W(*i++))
    if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &...tail) {
  _W(head);
  putchar(sizeof...(tail) ? ' ' : '\n');
  W(tail...);
}
int MOD = 1e9 + 7;
void ADD(long long &x, long long v) {
  x = (x + v) % MOD;
  if (x < 0) x += MOD;
}
int get_bit(long long x, int v) { return (x >> v) & 1; }
int main() {
  int n;
  R(n);
  vector<long long> AA(n);
  for (int i = 0; i < (n); ++i) {
    R(AA[i]);
  }
  long long ma = *max_element((AA).begin(), (AA).end());
  for (int i = 0; i < (n); ++i) {
    AA[i] = ma - AA[i];
  }
  sort((AA).begin(), (AA).end());
  long long mask = 0;
  long long two = 1;
  vector<pair<long long, long long> > dp{{0LL, 0LL}};
  for (int bit = 0; bit < (60); ++bit) {
    two <<= 1;
    mask |= 1LL << bit;
    vector<pair<long long, long long> > qq;
    for (int i = 0; i < (n); ++i) {
      if (get_bit(AA[i], bit)) {
        qq.push_back({0LL, 1LL});
        if (bit != 59) {
          qq.push_back({two - (mask & AA[i]), -1});
          if (two - (mask & AA[i]) + (two >> 1) < two)
            qq.push_back({two - (mask & AA[i]) + (two >> 1), 1});
        } else {
          if (two - (mask & AA[i]) + (two >> 1) < two)
            qq.push_back({two - (mask & AA[i]) + (two >> 1), 1});
        }
      } else {
        if (bit != 59) {
          qq.push_back({two / 2 - (mask & AA[i]), 1});
          if (mask & AA[i]) qq.push_back({two - (mask & AA[i]), -1});
        } else {
          qq.push_back({two / 2 - (mask & AA[i]), 1});
        }
      }
    }
    qq.push_back({0LL, 0LL});
    sort((qq).begin(), (qq).end());
    long long now = 0;
    vector<pair<long long, long long> > qq2;
    for (int i = 0, j; i < ((int)(qq).size()); i = j) {
      for (j = i; j < ((int)(qq).size()) && qq[i].first == qq[j].first; j++) {
        now += qq[j].second;
      }
      qq2.push_back({qq[i].first, now});
    }
    int m = ((int)(dp).size());
    for (int i = 0; i < (m); ++i)
      if (dp[i].first + (two / 2) < two)
        dp.push_back({dp[i].first + two / 2, dp[i].second});
    dp.push_back({two, 0});
    int it = 0;
    for (int i = 0; i < (((int)(qq2).size())); ++i) {
      long long mi = 1e18;
      while (dp[it + 1].first <= qq2[i].first) it++;
      long long nxt_v = two;
      if (i + 1 < ((int)(qq2).size())) nxt_v = qq2[i + 1].first;
      while (dp[it + 1].first < nxt_v) {
        mi = min(mi, dp[it].second);
        it++;
      }
      mi = min(mi, dp[it].second);
      qq2[i].second += mi;
    }
    dp = qq2;
  }
  long long an = 1e9;
  for (int i = 0; i < (((int)(dp).size())); ++i) {
    an = min(an, dp[i].second);
  }
  W(an);
  return 0;
}

### Prompt

Please create a solution in CPP to the following problem:

You are given n numbers a_1, a_2, ..., a_n. In one operation we can add to any one of those numbers a nonnegative integer power of 2.

What is the smallest number of operations we need to perform to make all n numbers equal? It can be proved that under given constraints it doesn't exceed 10^{18}.

Input

The first line contains a single integer n (1 ≤ n ≤ 10^5).

The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 10^{17}).

Output

Output exactly one integer — the smallest number of operations we need to perform to make all n numbers equal.

Examples

Input


4
228 228 228 228


Output


0

Input


3
2 2 8


Output


3

Note

In the first example, all numbers are already equal. So the needed number of operation is 0.

In the second example, we can apply the operation 3 times: add 8 to first 2, add 8 to second 2, add 2 to 8, making all numbers equal to 10. It can be proved that we can't make all numbers equal in less than 3 operations.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <class T>
void _R(T &x) {
  cin >> x;
}
void _R(int &x) { scanf("%d", &x); }
void _R(long long &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template <class T, class... U>
void R(T &head, U &...tail) {
  _R(head);
  R(tail...);
}
template <class T>
void _W(const T &x) {
  cout << x;
}
void _W(const int &x) { printf("%d", x); }
void _W(const long long &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T, class U>
void _W(const pair<T, U> &x) {
  _W(x.first);
  putchar(' ');
  _W(x.second);
}
template <class T>
void _W(const vector<T> &x) {
  for (auto i = x.begin(); i != x.end(); _W(*i++))
    if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &...tail) {
  _W(head);
  putchar(sizeof...(tail) ? ' ' : '\n');
  W(tail...);
}
int MOD = 1e9 + 7;
void ADD(long long &x, long long v) {
  x = (x + v) % MOD;
  if (x < 0) x += MOD;
}
int get_bit(long long x, int v) { return (x >> v) & 1; }
int main() {
  int n;
  R(n);
  vector<long long> AA(n);
  for (int i = 0; i < (n); ++i) {
    R(AA[i]);
  }
  long long ma = *max_element((AA).begin(), (AA).end());
  for (int i = 0; i < (n); ++i) {
    AA[i] = ma - AA[i];
  }
  sort((AA).begin(), (AA).end());
  long long mask = 0;
  long long two = 1;
  vector<pair<long long, long long> > dp{{0LL, 0LL}};
  for (int bit = 0; bit < (60); ++bit) {
    two <<= 1;
    mask |= 1LL << bit;
    vector<pair<long long, long long> > qq;
    for (int i = 0; i < (n); ++i) {
      if (get_bit(AA[i], bit)) {
        qq.push_back({0LL, 1LL});
        if (bit != 59) {
          qq.push_back({two - (mask & AA[i]), -1});
          if (two - (mask & AA[i]) + (two >> 1) < two)
            qq.push_back({two - (mask & AA[i]) + (two >> 1), 1});
        } else {
          if (two - (mask & AA[i]) + (two >> 1) < two)
            qq.push_back({two - (mask & AA[i]) + (two >> 1), 1});
        }
      } else {
        if (bit != 59) {
          qq.push_back({two / 2 - (mask & AA[i]), 1});
          if (mask & AA[i]) qq.push_back({two - (mask & AA[i]), -1});
        } else {
          qq.push_back({two / 2 - (mask & AA[i]), 1});
        }
      }
    }
    qq.push_back({0LL, 0LL});
    sort((qq).begin(), (qq).end());
    long long now = 0;
    vector<pair<long long, long long> > qq2;
    for (int i = 0, j; i < ((int)(qq).size()); i = j) {
      for (j = i; j < ((int)(qq).size()) && qq[i].first == qq[j].first; j++) {
        now += qq[j].second;
      }
      qq2.push_back({qq[i].first, now});
    }
    int m = ((int)(dp).size());
    for (int i = 0; i < (m); ++i)
      if (dp[i].first + (two / 2) < two)
        dp.push_back({dp[i].first + two / 2, dp[i].second});
    dp.push_back({two, 0});
    int it = 0;
    for (int i = 0; i < (((int)(qq2).size())); ++i) {
      long long mi = 1e18;
      while (dp[it + 1].first <= qq2[i].first) it++;
      long long nxt_v = two;
      if (i + 1 < ((int)(qq2).size())) nxt_v = qq2[i + 1].first;
      while (dp[it + 1].first < nxt_v) {
        mi = min(mi, dp[it].second);
        it++;
      }
      mi = min(mi, dp[it].second);
      qq2[i].second += mi;
    }
    dp = qq2;
  }
  long long an = 1e9;
  for (int i = 0; i < (((int)(dp).size())); ++i) {
    an = min(an, dp[i].second);
  }
  W(an);
  return 0;
}

```