#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class t, class u>
void chmax(t& first, u second) {
  if (first < second) first = second;
}
template <class t, class u>
void chmin(t& first, u second) {
  if (second < first) first = second;
}
template <class t>
using vc = vector<t>;
template <class t>
using vvc = vc<vc<t>>;
using pi = pair<ll, ll>;
using vi = vc<ll>;
template <class t, class u>
ostream& operator<<(ostream& os, const pair<t, u>& p) {
  return os << "{" << p.first << "," << p.second << "}";
}
template <class t>
ostream& operator<<(ostream& os, const vc<t>& v) {
  os << "{";
  for (auto e : v) os << e << ",";
  return os << "}";
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(20);
  const ll inf = LLONG_MAX / 3;
  ll n;
  cin >> n;
  vi first(n);
  for (ll i = ll(0); i < ll(n); i++) cin >> first[i];
  ll mx = *max_element(first.begin(), first.end());
  for (auto& v : first) v = mx - v;
  const ll L = 60;
  vvc<pi> rs(L);
  for (auto v : first)
    for (ll i = ll(0); i < ll(L); i++) {
      ll z = ll(1) << i;
      ll w = ((~v) & (z - 1)) + 1;
      if ((v >> i) & 1) {
        rs[i].emplace_back(0, w);
        rs[i].emplace_back(z + w, z * 2);
      } else
        rs[i].emplace_back(w, w + z);
      if (i == L - 1) rs[i].emplace_back((ll(1) << L) - v, ll(1) << L);
    }
  vi pos{0, ll(1) << L}, val{0};
  for (ll i = ll(L) - 1; i >= 0; i--) {
    void(0);
    void(0);
    void(0);
    ll z = ll(1) << i;
    sort(rs[i].begin(), rs[i].end());
    vi np;
    {
      vi tmp{z};
      for (auto r : rs[i]) {
        tmp.push_back(r.first);
        tmp.push_back(r.second);
      }
      sort(tmp.begin(), tmp.end());
      np.resize(tmp.size() + pos.size());
      merge(tmp.begin(), tmp.end(), pos.begin(), pos.end(), np.begin());
      np.erase(unique(np.begin(), np.end()), np.end());
    }
    vi nv(np.size() - 1);
    {
      ll j = 0;
      for (ll k = ll(0); k < ll(val.size()); k++)
        while (np[j] < pos[k + 1]) {
          nv[j] = val[k];
          j++;
        }
    }
    {
      for (ll j = ll(0); j < ll(rs[i].size() - 1); j++) {
        assert(rs[i][j].first <= rs[i][j + 1].first);
        assert(rs[i][j].second <= rs[i][j + 1].second);
      }
      vi ad(np.size());
      ll j = 0, k = 0;
      for (auto r : rs[i]) {
        while (np[j] < r.first) j++;
        while (np[k] < r.second) k++;
        ad[j]++;
        ad[k]--;
      }
      for (ll l = ll(0); l < ll(nv.size()); l++) {
        nv[l] += ad[l];
        ad[l + 1] += ad[l];
      }
    }
    void(0);
    void(0);
    {
      vi tmp = np;
      pos.resize(np.size());
      ll hal = 0;
      for (auto& p : tmp) {
        if (p >= z)
          p -= z;
        else
          hal++;
      }
      merge(tmp.begin(), tmp.begin() + hal, tmp.begin() + hal, tmp.end(),
            pos.begin());
      pos.erase(unique(pos.begin(), pos.end()), pos.end());
    }
    val.clear();
    val.resize(pos.size() - 1, inf);
    ll j = 0;
    for (ll k = ll(0); k < ll(nv.size()); k++) {
      if (np[k] == z) j = 0;
      ll w = np[k + 1];
      void(0);
      if (w > z) w -= z;
      void(0);
      void(0);
      void(0);
      void(0);
      while (pos[j] < w) {
        void(0);
        chmin(val[j], nv[k]);
        j++;
      }
    }
  }
  assert(pos.size() == 2);
  assert(val.size() == 1);
  cout << val[0] << endl;
}

### Prompt

Generate a cpp solution 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;
using ll = long long;
template <class t, class u>
void chmax(t& first, u second) {
  if (first < second) first = second;
}
template <class t, class u>
void chmin(t& first, u second) {
  if (second < first) first = second;
}
template <class t>
using vc = vector<t>;
template <class t>
using vvc = vc<vc<t>>;
using pi = pair<ll, ll>;
using vi = vc<ll>;
template <class t, class u>
ostream& operator<<(ostream& os, const pair<t, u>& p) {
  return os << "{" << p.first << "," << p.second << "}";
}
template <class t>
ostream& operator<<(ostream& os, const vc<t>& v) {
  os << "{";
  for (auto e : v) os << e << ",";
  return os << "}";
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(20);
  const ll inf = LLONG_MAX / 3;
  ll n;
  cin >> n;
  vi first(n);
  for (ll i = ll(0); i < ll(n); i++) cin >> first[i];
  ll mx = *max_element(first.begin(), first.end());
  for (auto& v : first) v = mx - v;
  const ll L = 60;
  vvc<pi> rs(L);
  for (auto v : first)
    for (ll i = ll(0); i < ll(L); i++) {
      ll z = ll(1) << i;
      ll w = ((~v) & (z - 1)) + 1;
      if ((v >> i) & 1) {
        rs[i].emplace_back(0, w);
        rs[i].emplace_back(z + w, z * 2);
      } else
        rs[i].emplace_back(w, w + z);
      if (i == L - 1) rs[i].emplace_back((ll(1) << L) - v, ll(1) << L);
    }
  vi pos{0, ll(1) << L}, val{0};
  for (ll i = ll(L) - 1; i >= 0; i--) {
    void(0);
    void(0);
    void(0);
    ll z = ll(1) << i;
    sort(rs[i].begin(), rs[i].end());
    vi np;
    {
      vi tmp{z};
      for (auto r : rs[i]) {
        tmp.push_back(r.first);
        tmp.push_back(r.second);
      }
      sort(tmp.begin(), tmp.end());
      np.resize(tmp.size() + pos.size());
      merge(tmp.begin(), tmp.end(), pos.begin(), pos.end(), np.begin());
      np.erase(unique(np.begin(), np.end()), np.end());
    }
    vi nv(np.size() - 1);
    {
      ll j = 0;
      for (ll k = ll(0); k < ll(val.size()); k++)
        while (np[j] < pos[k + 1]) {
          nv[j] = val[k];
          j++;
        }
    }
    {
      for (ll j = ll(0); j < ll(rs[i].size() - 1); j++) {
        assert(rs[i][j].first <= rs[i][j + 1].first);
        assert(rs[i][j].second <= rs[i][j + 1].second);
      }
      vi ad(np.size());
      ll j = 0, k = 0;
      for (auto r : rs[i]) {
        while (np[j] < r.first) j++;
        while (np[k] < r.second) k++;
        ad[j]++;
        ad[k]--;
      }
      for (ll l = ll(0); l < ll(nv.size()); l++) {
        nv[l] += ad[l];
        ad[l + 1] += ad[l];
      }
    }
    void(0);
    void(0);
    {
      vi tmp = np;
      pos.resize(np.size());
      ll hal = 0;
      for (auto& p : tmp) {
        if (p >= z)
          p -= z;
        else
          hal++;
      }
      merge(tmp.begin(), tmp.begin() + hal, tmp.begin() + hal, tmp.end(),
            pos.begin());
      pos.erase(unique(pos.begin(), pos.end()), pos.end());
    }
    val.clear();
    val.resize(pos.size() - 1, inf);
    ll j = 0;
    for (ll k = ll(0); k < ll(nv.size()); k++) {
      if (np[k] == z) j = 0;
      ll w = np[k + 1];
      void(0);
      if (w > z) w -= z;
      void(0);
      void(0);
      void(0);
      void(0);
      while (pos[j] < w) {
        void(0);
        chmin(val[j], nv[k]);
        j++;
      }
    }
  }
  assert(pos.size() == 2);
  assert(val.size() == 1);
  cout << val[0] << endl;
}

```