#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int v = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    v = v * 10 + c - '0';
    c = getchar();
  }
  return v * f;
}
const int Maxn = 100005;
int n;
long long a[Maxn];
long long c[66][Maxn];
int s1[66];
int pn[66][Maxn];
int dp[66][Maxn];
void Ckmin(int &x, int y) {
  if (y < x) x = y;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
  }
  sort(a + 1, a + 1 + n);
  long long tmpp = a[n];
  for (int i = 1; i <= n; i++) {
    a[i] = tmpp - a[i];
  }
  for (int i = 0; i <= 61; i++) {
    long long tmp = (1ll << (i + 1)) - 1;
    for (int j = 1; j <= n; j++) {
      c[i][j] = a[j] & tmp;
    }
    sort(c[i] + 1, c[i] + 1 + n);
    s1[i] = n + 1;
    for (int j = 1; j <= n; j++) {
      if (c[i][j] >> i & 1) {
        s1[i] = j;
        break;
      }
    }
  }
  for (int i = 0; i <= 61; i++) {
    long long tmp = (1ll << i) - 1;
    for (int j = 1; j <= n; j++) {
      if (!i) {
        pn[i][j] = 0;
      } else {
        pn[i][j] = lower_bound(c[i - 1] + 1, c[i - 1] + 1 + n, c[i][j] & tmp) -
                   c[i - 1];
        assert(c[i - 1][pn[i][j]] == (c[i][j] & tmp));
      }
    }
  }
  for (int i = 0; i < 66; i++) {
    for (int j = 0; j < Maxn; j++) {
      dp[i][j] = 1e9;
    }
  }
  dp[0][1] = 0;
  int ans = 1e9;
  for (int i = 0; i <= 61; i++) {
    for (int j = 0; j < Maxn; j++) {
      if (i == 61 && j == n + 1) Ckmin(ans, dp[i][j]);
      if (dp[i][j] != 1e9) {
        int lo = 0, hi = s1[i];
        while (hi - lo > 1) {
          int mid = lo + hi >> 1;
          if (j <= pn[i][mid]) {
            hi = mid;
          } else {
            lo = mid;
          }
        }
        int bound0 = lo;
        lo = s1[i] - 1, hi = n + 1;
        while (hi - lo > 1) {
          int mid = lo + hi >> 1;
          if (j <= pn[i][mid]) {
            hi = mid;
          } else {
            lo = mid;
          }
        }
        int bound1 = lo;
        Ckmin(dp[i + 1][bound1 + 1], dp[i][j] + max(0, (s1[i] - bound0 - 1)) +
                                         max(0, (bound1 - s1[i] + 1)));
        Ckmin(dp[i + 1][bound0 + 1],
              dp[i][j] + max(0, (bound0 - 1 + 1)) + max(0, (n - bound1)));
      }
    }
  }
  printf("%d\n", ans);
  return 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;
inline int read() {
  int v = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    v = v * 10 + c - '0';
    c = getchar();
  }
  return v * f;
}
const int Maxn = 100005;
int n;
long long a[Maxn];
long long c[66][Maxn];
int s1[66];
int pn[66][Maxn];
int dp[66][Maxn];
void Ckmin(int &x, int y) {
  if (y < x) x = y;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
  }
  sort(a + 1, a + 1 + n);
  long long tmpp = a[n];
  for (int i = 1; i <= n; i++) {
    a[i] = tmpp - a[i];
  }
  for (int i = 0; i <= 61; i++) {
    long long tmp = (1ll << (i + 1)) - 1;
    for (int j = 1; j <= n; j++) {
      c[i][j] = a[j] & tmp;
    }
    sort(c[i] + 1, c[i] + 1 + n);
    s1[i] = n + 1;
    for (int j = 1; j <= n; j++) {
      if (c[i][j] >> i & 1) {
        s1[i] = j;
        break;
      }
    }
  }
  for (int i = 0; i <= 61; i++) {
    long long tmp = (1ll << i) - 1;
    for (int j = 1; j <= n; j++) {
      if (!i) {
        pn[i][j] = 0;
      } else {
        pn[i][j] = lower_bound(c[i - 1] + 1, c[i - 1] + 1 + n, c[i][j] & tmp) -
                   c[i - 1];
        assert(c[i - 1][pn[i][j]] == (c[i][j] & tmp));
      }
    }
  }
  for (int i = 0; i < 66; i++) {
    for (int j = 0; j < Maxn; j++) {
      dp[i][j] = 1e9;
    }
  }
  dp[0][1] = 0;
  int ans = 1e9;
  for (int i = 0; i <= 61; i++) {
    for (int j = 0; j < Maxn; j++) {
      if (i == 61 && j == n + 1) Ckmin(ans, dp[i][j]);
      if (dp[i][j] != 1e9) {
        int lo = 0, hi = s1[i];
        while (hi - lo > 1) {
          int mid = lo + hi >> 1;
          if (j <= pn[i][mid]) {
            hi = mid;
          } else {
            lo = mid;
          }
        }
        int bound0 = lo;
        lo = s1[i] - 1, hi = n + 1;
        while (hi - lo > 1) {
          int mid = lo + hi >> 1;
          if (j <= pn[i][mid]) {
            hi = mid;
          } else {
            lo = mid;
          }
        }
        int bound1 = lo;
        Ckmin(dp[i + 1][bound1 + 1], dp[i][j] + max(0, (s1[i] - bound0 - 1)) +
                                         max(0, (bound1 - s1[i] + 1)));
        Ckmin(dp[i + 1][bound0 + 1],
              dp[i][j] + max(0, (bound0 - 1 + 1)) + max(0, (n - bound1)));
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}

```