#include <bits/stdc++.h>
using namespace std;
long long a[100010], M;
int f[70][100010], n, p1[100010], p[100010], as = 1e9 + 1, m;
bool Cmp(int x, int y) { return (a[x] % M > a[y] % M); }
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
  memset(f, 31, sizeof(f));
  int nm = 0;
  for (int i = 1; i <= n; i++)
    if (!(a[i] & 1)) nm++;
  f[0][0] = nm, f[0][n - nm] = n - nm;
  for (int i = 1; i <= 60; i++) {
    for (int j = 1; j <= n; j++) p[j] = j;
    M = 1ll << i;
    sort(p + 1, p + 1 + n, Cmp);
    for (int j = 1; j <= n; j++) p1[j] = p[j];
    int nm1 = 0, nm0 = 0, ck = 1;
    for (int j = 1; j <= n; j++) {
      if ((a[j] >> i) & 1) nm1++;
      if (a[j] >= (1ll << i + 1)) ck = 0;
    }
    nm0 = n - nm1;
    for (int w1 = 0, w0 = nm1, j = 0; j <= n; j++) {
      if (j) {
        int jj = p1[j];
        if ((a[jj] >> i) & 1)
          w1++, nm1--, nm0++;
        else
          nm0--, w0++, nm1++;
      }
      if (f[i][w1] > f[i - 1][j] + nm0) {
        f[i][w1] = f[i - 1][j] + nm0;
      }
      if (f[i][w0] > f[i - 1][j] + nm1) {
        f[i][w0] = f[i - 1][j] + nm1;
      }
    }
    if (ck && as > f[i][0]) as = f[i][0];
  }
  printf("%d\n", as);
}

### Prompt

Develop a solution in Cpp to the problem described below:

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;
long long a[100010], M;
int f[70][100010], n, p1[100010], p[100010], as = 1e9 + 1, m;
bool Cmp(int x, int y) { return (a[x] % M > a[y] % M); }
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
  memset(f, 31, sizeof(f));
  int nm = 0;
  for (int i = 1; i <= n; i++)
    if (!(a[i] & 1)) nm++;
  f[0][0] = nm, f[0][n - nm] = n - nm;
  for (int i = 1; i <= 60; i++) {
    for (int j = 1; j <= n; j++) p[j] = j;
    M = 1ll << i;
    sort(p + 1, p + 1 + n, Cmp);
    for (int j = 1; j <= n; j++) p1[j] = p[j];
    int nm1 = 0, nm0 = 0, ck = 1;
    for (int j = 1; j <= n; j++) {
      if ((a[j] >> i) & 1) nm1++;
      if (a[j] >= (1ll << i + 1)) ck = 0;
    }
    nm0 = n - nm1;
    for (int w1 = 0, w0 = nm1, j = 0; j <= n; j++) {
      if (j) {
        int jj = p1[j];
        if ((a[jj] >> i) & 1)
          w1++, nm1--, nm0++;
        else
          nm0--, w0++, nm1++;
      }
      if (f[i][w1] > f[i - 1][j] + nm0) {
        f[i][w1] = f[i - 1][j] + nm0;
      }
      if (f[i][w0] > f[i - 1][j] + nm1) {
        f[i][w0] = f[i - 1][j] + nm1;
      }
    }
    if (ck && as > f[i][0]) as = f[i][0];
  }
  printf("%d\n", as);
}

```