#include <bits/stdc++.h>
using namespace std;
inline char gc() {
  static char now[1 << 16], *S, *T;
  if (S == T) {
    T = (S = now) + fread(now, 1, 1 << 16, stdin);
    if (S == T) return EOF;
  }
  return *S++;
}
inline long long read() {
  long long x = 0, f = 1;
  char c = gc();
  while (c < '0' || c > '9') {
    (c == '-') ? (f = 0) : 0;
    c = gc();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 3) + (x << 1) + (c ^ 48);
    c = gc();
  }
  return f ? x : ((~x) + 1);
}
const int mod = 1e9 + 7;
inline int add(const int &x, const int &y) {
  return (x + y >= mod) ? (x + y - mod) : (x + y);
}
inline void Add(int &x, const int &y) {
  x += y;
  (x >= mod) ? (x -= mod) : 0;
}
inline int sub(const int &x, const int &y) {
  return (x < y) ? (x - y + mod) : (x - y);
}
inline void Sub(int &x, const int &y) {
  x -= y;
  (x < 0) ? (x += mod) : 0;
}
inline int qpow(int a, int b) {
  if (!a) return 0;
  int res = 1;
  for (; b; b >>= 1, a = 1ll * a * a % mod)
    if (b & 1) res = 1ll * res * a % mod;
  return res;
}
const int N = 100010;
const int lim = 62;
const long long inf = 1ll << lim;
int n;
long long a[N], f[lim + 10][N];
int main() {
  n = read();
  long long mx = 0;
  for (int(i) = (1); (i) <= (n); ++(i)) {
    a[i] = read();
    (mx) = max((mx), (a[i]));
  }
  for (int(i) = (1); (i) <= (n); ++(i)) a[i] = mx - a[i];
  for (int(i) = (0); (i) <= (lim + 1); ++(i))
    for (int(j) = (0); (j) <= (n); ++(j)) f[i][j] = inf;
  f[0][0] = 0;
  vector<int> bin;
  for (int(i) = (1); (i) <= (n); ++(i)) bin.push_back(i);
  for (int(d) = (0); (d) <= (lim); ++(d)) {
    if (d) {
      vector<int> tmp;
      for (int now : bin)
        if (!(a[now] & (1ll << (d - 1)))) {
          tmp.push_back(now);
        }
      for (int now : bin)
        if (a[now] & (1ll << (d - 1))) {
          tmp.push_back(now);
        }
      bin = tmp;
    }
    vector<int> sum0(n + 1), sum1(n + 1);
    sum0[0] = sum1[0] = 0;
    for (int(i) = (1); (i) <= (n); ++(i)) {
      sum0[i] = sum0[i - 1] + (!(a[bin[i - 1]] >> d & 1ll));
      sum1[i] = sum1[i - 1] + (a[bin[i - 1]] >> d & 1ll);
    }
    int tot0 = sum0[n], tot1 = sum1[n];
    for (int(i) = (0); (i) <= (n); ++(i))
      if (f[d][i] ^ inf) {
        for (int(now) = (0); (now) <= (1); ++(now)) {
          if (!now) {
            int delta = tot0 - sum0[n - i] + sum1[n - i];
            (f[d + 1][tot1 - sum1[n - i]]) =
                min((f[d + 1][tot1 - sum1[n - i]]), (f[d][i] + delta));
          } else {
            int delta = tot1 - sum1[n - i] + sum0[n - i];
            (f[d + 1][n - sum0[n - i]]) =
                min((f[d + 1][n - sum0[n - i]]), (f[d][i] + delta));
          }
        }
      }
  }
  printf("%I64d\n", f[lim + 1][0]);
  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 char gc() {
  static char now[1 << 16], *S, *T;
  if (S == T) {
    T = (S = now) + fread(now, 1, 1 << 16, stdin);
    if (S == T) return EOF;
  }
  return *S++;
}
inline long long read() {
  long long x = 0, f = 1;
  char c = gc();
  while (c < '0' || c > '9') {
    (c == '-') ? (f = 0) : 0;
    c = gc();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 3) + (x << 1) + (c ^ 48);
    c = gc();
  }
  return f ? x : ((~x) + 1);
}
const int mod = 1e9 + 7;
inline int add(const int &x, const int &y) {
  return (x + y >= mod) ? (x + y - mod) : (x + y);
}
inline void Add(int &x, const int &y) {
  x += y;
  (x >= mod) ? (x -= mod) : 0;
}
inline int sub(const int &x, const int &y) {
  return (x < y) ? (x - y + mod) : (x - y);
}
inline void Sub(int &x, const int &y) {
  x -= y;
  (x < 0) ? (x += mod) : 0;
}
inline int qpow(int a, int b) {
  if (!a) return 0;
  int res = 1;
  for (; b; b >>= 1, a = 1ll * a * a % mod)
    if (b & 1) res = 1ll * res * a % mod;
  return res;
}
const int N = 100010;
const int lim = 62;
const long long inf = 1ll << lim;
int n;
long long a[N], f[lim + 10][N];
int main() {
  n = read();
  long long mx = 0;
  for (int(i) = (1); (i) <= (n); ++(i)) {
    a[i] = read();
    (mx) = max((mx), (a[i]));
  }
  for (int(i) = (1); (i) <= (n); ++(i)) a[i] = mx - a[i];
  for (int(i) = (0); (i) <= (lim + 1); ++(i))
    for (int(j) = (0); (j) <= (n); ++(j)) f[i][j] = inf;
  f[0][0] = 0;
  vector<int> bin;
  for (int(i) = (1); (i) <= (n); ++(i)) bin.push_back(i);
  for (int(d) = (0); (d) <= (lim); ++(d)) {
    if (d) {
      vector<int> tmp;
      for (int now : bin)
        if (!(a[now] & (1ll << (d - 1)))) {
          tmp.push_back(now);
        }
      for (int now : bin)
        if (a[now] & (1ll << (d - 1))) {
          tmp.push_back(now);
        }
      bin = tmp;
    }
    vector<int> sum0(n + 1), sum1(n + 1);
    sum0[0] = sum1[0] = 0;
    for (int(i) = (1); (i) <= (n); ++(i)) {
      sum0[i] = sum0[i - 1] + (!(a[bin[i - 1]] >> d & 1ll));
      sum1[i] = sum1[i - 1] + (a[bin[i - 1]] >> d & 1ll);
    }
    int tot0 = sum0[n], tot1 = sum1[n];
    for (int(i) = (0); (i) <= (n); ++(i))
      if (f[d][i] ^ inf) {
        for (int(now) = (0); (now) <= (1); ++(now)) {
          if (!now) {
            int delta = tot0 - sum0[n - i] + sum1[n - i];
            (f[d + 1][tot1 - sum1[n - i]]) =
                min((f[d + 1][tot1 - sum1[n - i]]), (f[d][i] + delta));
          } else {
            int delta = tot1 - sum1[n - i] + sum0[n - i];
            (f[d + 1][n - sum0[n - i]]) =
                min((f[d + 1][n - sum0[n - i]]), (f[d][i] + delta));
          }
        }
      }
  }
  printf("%I64d\n", f[lim + 1][0]);
  return 0;
}

```