#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;
template <typename T>
void ckmin(T& a, const T& b) {
  a = min(a, b);
}
template <typename T>
void ckmax(T& a, const T& b) {
  a = max(a, b);
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace __input {
template <typename T1, typename T2>
istream& operator>>(istream& i, pair<T1, T2>& p) {
  i >> p.first >> p.second;
  return i;
}
template <typename T, size_t N>
istream& operator>>(istream& i, array<T, N>& v) {
  for (auto& e : v) {
    i >> e;
  }
  return i;
}
template <typename T>
istream& operator>>(istream& i, vector<T>& v) {
  for (auto& e : v) {
    i >> e;
  }
  return i;
}
}  // namespace __input
using namespace __input;
namespace __output {
template <typename T1, typename T2>
ostream& operator<<(ostream& o, const pair<T1, T2>& t) {
  return o << "(" << t.first << ", " << t.second << ")";
}
template <typename T, size_t N>
ostream& operator<<(ostream& o, const array<T, N>& a) {
  o << "[";
  for (int i = 0; i < N; i++) {
    if (i) o << ", ";
    o << a[i];
  }
  return o << "]";
}
template <typename T>
ostream& operator<<(ostream& o, const vector<T>& v) {
  o << "[";
  for (int i = 0; i < int((v).size()); i++) {
    if (i) o << ", ";
    o << v[i];
  }
  return o << "]";
}
}  // namespace __output
using namespace __output;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  const int BITS = 62;
  int N;
  cin >> N;
  vll vals(N);
  cin >> vals;
  vvll at(BITS);
  vll uniq;
  for (int i = 0; i < (BITS); i++) {
    at[i] = vals;
    const ll MASK = (1ll << i) - 1;
    sort((at[i]).begin(), (at[i]).end(),
         [&](ll a, ll b) { return (a & MASK) < (b & MASK); });
    for (auto& v : vals) uniq.push_back(v & MASK);
  }
  sort((uniq).begin(), (uniq).end());
  uniq.erase(unique((uniq).begin(), (uniq).end()), uniq.end());
  struct state {
    ll l, c;
    bool operator<(const state& o) const { return l < o.l; }
  };
  vector<state> dp, succ;
  for (auto& v : uniq) {
    dp.push_back({v, LLONG_MAX / 2});
    succ.push_back({v, LLONG_MAX / 2});
  }
  dp[0].c = 0;
  for (int i = 0; i < (BITS - 1); i++) {
    const ll MASK = (1ll << i) - 1;
    for (auto& v : succ) v.c = LLONG_MAX / 2;
    int zero = 0, one = 0;
    for (auto& v : vals)
      if (v & (1ll << i))
        one++;
      else
        zero++;
    int j = 0, zblw = 0, oblw = 0;
    int s1 = 0, s2 = 0;
    for (auto& s : dp) {
      while (j < N && (at[i][j] & MASK) <= s.l) {
        if (at[i][j] & (1ll << i))
          oblw++;
        else
          zblw++;
        j++;
      }
      while (s1 + 1 < int((succ).size()) && succ[s1 + 1].l <= s.l) s1++;
      while (s2 + 1 < int((succ).size()) && succ[s2 + 1].l <= s.l + (1ll << i))
        s2++;
      ckmin(succ[s1].c, s.c + oblw + zero - zblw);
      ckmin(succ[s2].c, s.c + zblw + one - oblw);
    }
    swap(dp, succ);
  }
  ll ans = LLONG_MAX;
  for (auto& s : dp)
    if (s.l >= uniq.back()) ckmin(ans, s.c);
  cout << ans << endl;
  return 0;
}

### Prompt

Create a solution in cpp for 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;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;
template <typename T>
void ckmin(T& a, const T& b) {
  a = min(a, b);
}
template <typename T>
void ckmax(T& a, const T& b) {
  a = max(a, b);
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace __input {
template <typename T1, typename T2>
istream& operator>>(istream& i, pair<T1, T2>& p) {
  i >> p.first >> p.second;
  return i;
}
template <typename T, size_t N>
istream& operator>>(istream& i, array<T, N>& v) {
  for (auto& e : v) {
    i >> e;
  }
  return i;
}
template <typename T>
istream& operator>>(istream& i, vector<T>& v) {
  for (auto& e : v) {
    i >> e;
  }
  return i;
}
}  // namespace __input
using namespace __input;
namespace __output {
template <typename T1, typename T2>
ostream& operator<<(ostream& o, const pair<T1, T2>& t) {
  return o << "(" << t.first << ", " << t.second << ")";
}
template <typename T, size_t N>
ostream& operator<<(ostream& o, const array<T, N>& a) {
  o << "[";
  for (int i = 0; i < N; i++) {
    if (i) o << ", ";
    o << a[i];
  }
  return o << "]";
}
template <typename T>
ostream& operator<<(ostream& o, const vector<T>& v) {
  o << "[";
  for (int i = 0; i < int((v).size()); i++) {
    if (i) o << ", ";
    o << v[i];
  }
  return o << "]";
}
}  // namespace __output
using namespace __output;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  const int BITS = 62;
  int N;
  cin >> N;
  vll vals(N);
  cin >> vals;
  vvll at(BITS);
  vll uniq;
  for (int i = 0; i < (BITS); i++) {
    at[i] = vals;
    const ll MASK = (1ll << i) - 1;
    sort((at[i]).begin(), (at[i]).end(),
         [&](ll a, ll b) { return (a & MASK) < (b & MASK); });
    for (auto& v : vals) uniq.push_back(v & MASK);
  }
  sort((uniq).begin(), (uniq).end());
  uniq.erase(unique((uniq).begin(), (uniq).end()), uniq.end());
  struct state {
    ll l, c;
    bool operator<(const state& o) const { return l < o.l; }
  };
  vector<state> dp, succ;
  for (auto& v : uniq) {
    dp.push_back({v, LLONG_MAX / 2});
    succ.push_back({v, LLONG_MAX / 2});
  }
  dp[0].c = 0;
  for (int i = 0; i < (BITS - 1); i++) {
    const ll MASK = (1ll << i) - 1;
    for (auto& v : succ) v.c = LLONG_MAX / 2;
    int zero = 0, one = 0;
    for (auto& v : vals)
      if (v & (1ll << i))
        one++;
      else
        zero++;
    int j = 0, zblw = 0, oblw = 0;
    int s1 = 0, s2 = 0;
    for (auto& s : dp) {
      while (j < N && (at[i][j] & MASK) <= s.l) {
        if (at[i][j] & (1ll << i))
          oblw++;
        else
          zblw++;
        j++;
      }
      while (s1 + 1 < int((succ).size()) && succ[s1 + 1].l <= s.l) s1++;
      while (s2 + 1 < int((succ).size()) && succ[s2 + 1].l <= s.l + (1ll << i))
        s2++;
      ckmin(succ[s1].c, s.c + oblw + zero - zblw);
      ckmin(succ[s2].c, s.c + zblw + one - oblw);
    }
    swap(dp, succ);
  }
  ll ans = LLONG_MAX;
  for (auto& s : dp)
    if (s.l >= uniq.back()) ckmin(ans, s.c);
  cout << ans << endl;
  return 0;
}

```