#include <bits/stdc++.h>
using namespace std;
const int bzmax = 62;
const int N = 1e5 + 5;
const signed int inf = (signed)(~0u >> 1);
template <typename T>
void smin(T& a, T b) {
  (a > b) && (a = b, 0);
}
int n;
int f[2][N];
long long a[N], b[N], c[N];
void bsort(int k) {
  int s = 1, t = n;
  for (int i = 1; i <= n; i++) {
    c[i] = a[i];
    if ((a[i] >> k) & 1) {
      b[s++] = a[i];
    } else {
      b[t--] = a[i];
    }
  }
  reverse(b + t + 1, b + n + 1);
  for (int i = 1; i <= n; i++) {
    a[i] = b[i];
  }
}
int main() {
  scanf("%d", &n);
  long long mx = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%lld", a + i);
    mx = max(a[i], mx);
  }
  for (int i = 1; i <= n; i++) {
    a[i] = mx - a[i];
  }
  int *flst = f[0], *fcur = f[1];
  for (int i = 1; i <= n; i++) fcur[i] = inf;
  for (int t = 0; t < bzmax; t++) {
    swap(fcur, flst);
    for (int i = 0; i <= n; i++) {
      fcur[i] = inf;
    }
    bsort(t);
    int one = 1, pone = 0;
    while ((a[one] >> t) & 1) one++;
    one--;
    for (int i = 0; i <= n; i++) {
      pone += (c[i] >> t) & 1;
      if (flst[i] ^ inf) {
        int cost = i - pone + one - pone;
        smin(fcur[pone], flst[i] + cost);
        smin(fcur[i + one - pone], flst[i] + n - cost);
      }
    }
  }
  printf("%d\n", fcur[0]);
  return 0;
}

### Prompt

Please formulate 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;
const int bzmax = 62;
const int N = 1e5 + 5;
const signed int inf = (signed)(~0u >> 1);
template <typename T>
void smin(T& a, T b) {
  (a > b) && (a = b, 0);
}
int n;
int f[2][N];
long long a[N], b[N], c[N];
void bsort(int k) {
  int s = 1, t = n;
  for (int i = 1; i <= n; i++) {
    c[i] = a[i];
    if ((a[i] >> k) & 1) {
      b[s++] = a[i];
    } else {
      b[t--] = a[i];
    }
  }
  reverse(b + t + 1, b + n + 1);
  for (int i = 1; i <= n; i++) {
    a[i] = b[i];
  }
}
int main() {
  scanf("%d", &n);
  long long mx = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%lld", a + i);
    mx = max(a[i], mx);
  }
  for (int i = 1; i <= n; i++) {
    a[i] = mx - a[i];
  }
  int *flst = f[0], *fcur = f[1];
  for (int i = 1; i <= n; i++) fcur[i] = inf;
  for (int t = 0; t < bzmax; t++) {
    swap(fcur, flst);
    for (int i = 0; i <= n; i++) {
      fcur[i] = inf;
    }
    bsort(t);
    int one = 1, pone = 0;
    while ((a[one] >> t) & 1) one++;
    one--;
    for (int i = 0; i <= n; i++) {
      pone += (c[i] >> t) & 1;
      if (flst[i] ^ inf) {
        int cost = i - pone + one - pone;
        smin(fcur[pone], flst[i] + cost);
        smin(fcur[i + one - pone], flst[i] + n - cost);
      }
    }
  }
  printf("%d\n", fcur[0]);
  return 0;
}

```