#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10, inf = 1e9;
int dp[maxn], n;
int val[2 * maxn];
pair<long long, int> a[maxn];
vector<pair<long long, int> > v0, v1;
void build() {
  for (int i = 0; i < maxn; i++) val[i + maxn] = dp[i] + i;
  for (int i = maxn - 1; i > 0; i--) val[i] = min(val[2 * i], val[2 * i + 1]);
}
int ask(int f, int s) {
  int ans = inf;
  for (f += maxn, s += maxn; f < s; f >>= 1, s >>= 1) {
    if (f & 1) ans = min(ans, val[f++]);
    if (s & 1) ans = min(ans, val[--s]);
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    dp[i] = inf;
  }
  dp[0] = 0;
  build();
  long long mx = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i].first;
    a[i].second = i;
    mx = max(mx, a[i].first);
  }
  for (int i = 0; i < n; i++) {
    a[i].first = mx - a[i].first;
  }
  for (int q = 0; q <= 60; q++) {
    for (int i = 0; i < n; i++) {
      a[i].second = i + 1;
    }
    v0.clear(), v1.clear();
    for (int i = 0; i < n; i++) {
      if ((((a[i].first) >> (q)) & 1) == 0)
        v1.push_back(a[i]);
      else
        v0.push_back(a[i]);
    }
    for (int i = 0; i <= n; i++) dp[i] = inf;
    int lst = 0;
    for (int i = 0; i < int((v0).size()); i++)
      dp[i] = ask(lst, v0[i].second) + int((v0).size()) - 2 * i,
      lst = v0[i].second;
    dp[int((v0).size())] = ask(lst, n + 1) - int((v0).size());
    lst = int((v1).size()) ? v1[0].second : n + 1;
    dp[int((v0).size())] =
        min(dp[int((v0).size())], ask(0, lst) + int((v1).size()));
    lst = n + 1;
    for (int i = int((v1).size()) - 1; i >= 0; i--)
      dp[int((v0).size()) + 1 + i] =
          ask(v1[i].second, lst) + int((v1).size()) - 2 * (i + 1),
                                lst = v1[i].second;
    int cc = 0;
    for (auto x : v0) a[cc++] = x;
    for (auto x : v1) a[cc++] = x;
    build();
  }
  return cout << ask(0, n + 1) << endl, 0;
}

### Prompt

In Cpp, your task is to solve 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;
const int maxn = 1e5 + 10, inf = 1e9;
int dp[maxn], n;
int val[2 * maxn];
pair<long long, int> a[maxn];
vector<pair<long long, int> > v0, v1;
void build() {
  for (int i = 0; i < maxn; i++) val[i + maxn] = dp[i] + i;
  for (int i = maxn - 1; i > 0; i--) val[i] = min(val[2 * i], val[2 * i + 1]);
}
int ask(int f, int s) {
  int ans = inf;
  for (f += maxn, s += maxn; f < s; f >>= 1, s >>= 1) {
    if (f & 1) ans = min(ans, val[f++]);
    if (s & 1) ans = min(ans, val[--s]);
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    dp[i] = inf;
  }
  dp[0] = 0;
  build();
  long long mx = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i].first;
    a[i].second = i;
    mx = max(mx, a[i].first);
  }
  for (int i = 0; i < n; i++) {
    a[i].first = mx - a[i].first;
  }
  for (int q = 0; q <= 60; q++) {
    for (int i = 0; i < n; i++) {
      a[i].second = i + 1;
    }
    v0.clear(), v1.clear();
    for (int i = 0; i < n; i++) {
      if ((((a[i].first) >> (q)) & 1) == 0)
        v1.push_back(a[i]);
      else
        v0.push_back(a[i]);
    }
    for (int i = 0; i <= n; i++) dp[i] = inf;
    int lst = 0;
    for (int i = 0; i < int((v0).size()); i++)
      dp[i] = ask(lst, v0[i].second) + int((v0).size()) - 2 * i,
      lst = v0[i].second;
    dp[int((v0).size())] = ask(lst, n + 1) - int((v0).size());
    lst = int((v1).size()) ? v1[0].second : n + 1;
    dp[int((v0).size())] =
        min(dp[int((v0).size())], ask(0, lst) + int((v1).size()));
    lst = n + 1;
    for (int i = int((v1).size()) - 1; i >= 0; i--)
      dp[int((v0).size()) + 1 + i] =
          ask(v1[i].second, lst) + int((v1).size()) - 2 * (i + 1),
                                lst = v1[i].second;
    int cc = 0;
    for (auto x : v0) a[cc++] = x;
    for (auto x : v1) a[cc++] = x;
    build();
  }
  return cout << ask(0, n + 1) << endl, 0;
}

```