#include <bits/stdc++.h>
using std::make_pair;
using std::max;
using std::min;
using std::multiset;
using std::pair;
using std::sort;
using std::swap;
using std::vector;
long long read() {
  int f = 1;
  long long h = 0;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') h = (h << 1) + (h << 3) + c - '0', c = getchar();
  return h * f;
}
const int MAXN = 101000;
int n;
long long a[MAXN];
int f[61][MAXN];
int W;
bool cmp(long long x, long long y) {
  return (x & ((1ll << W) - 1)) > (y & ((1ll << W) - 1));
}
long long mxa;
int main() {
  n = read();
  for (int i = 1; i <= n; i++) a[i] = read(), mxa = max(mxa, a[i]);
  for (int i = 1; i <= n; i++) a[i] = mxa - a[i];
  memset(f, 0x3f, sizeof(f));
  f[0][0] = 0;
  for (int w = 1; w <= 60; w++) {
    W = w - 1;
    sort(a + 1, a + n + 1, cmp);
    int cnt = 0, jw = 0;
    for (int i = 1; i <= n; i++) {
      if ((a[i] >> (w - 1)) & 1)
        cnt++;
      else
        ;
    }
    f[w][jw] = min(f[w][jw], f[w - 1][0] + cnt);
    for (int i = 1; i <= n; i++) {
      if ((a[i] >> (w - 1)) & 1)
        cnt--;
      else
        ;
      if ((a[i] >> (w - 1)) & 1)
        jw++;
      else
        cnt++;
      f[w][jw] = min(f[w][jw], f[w - 1][i] + cnt);
    }
    cnt = 0, jw = 0;
    for (int i = 1; i <= n; i++) {
      if ((a[i] >> (w - 1)) & 1)
        jw++;
      else
        cnt++;
    }
    f[w][jw] = min(f[w][jw], f[w - 1][0] + cnt);
    for (int i = 1; i <= n; i++) {
      if ((a[i] >> (w - 1)) & 1)
        jw--;
      else
        cnt--;
      if ((a[i] >> (w - 1)) & 1)
        cnt++, jw++;
      else
        jw++;
      f[w][jw] = min(f[w][jw], f[w - 1][i] + cnt);
    }
  }
  printf("%d\n", f[60][0]);
  return 0;
}

### Prompt

Your task is to create 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 std::make_pair;
using std::max;
using std::min;
using std::multiset;
using std::pair;
using std::sort;
using std::swap;
using std::vector;
long long read() {
  int f = 1;
  long long h = 0;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') h = (h << 1) + (h << 3) + c - '0', c = getchar();
  return h * f;
}
const int MAXN = 101000;
int n;
long long a[MAXN];
int f[61][MAXN];
int W;
bool cmp(long long x, long long y) {
  return (x & ((1ll << W) - 1)) > (y & ((1ll << W) - 1));
}
long long mxa;
int main() {
  n = read();
  for (int i = 1; i <= n; i++) a[i] = read(), mxa = max(mxa, a[i]);
  for (int i = 1; i <= n; i++) a[i] = mxa - a[i];
  memset(f, 0x3f, sizeof(f));
  f[0][0] = 0;
  for (int w = 1; w <= 60; w++) {
    W = w - 1;
    sort(a + 1, a + n + 1, cmp);
    int cnt = 0, jw = 0;
    for (int i = 1; i <= n; i++) {
      if ((a[i] >> (w - 1)) & 1)
        cnt++;
      else
        ;
    }
    f[w][jw] = min(f[w][jw], f[w - 1][0] + cnt);
    for (int i = 1; i <= n; i++) {
      if ((a[i] >> (w - 1)) & 1)
        cnt--;
      else
        ;
      if ((a[i] >> (w - 1)) & 1)
        jw++;
      else
        cnt++;
      f[w][jw] = min(f[w][jw], f[w - 1][i] + cnt);
    }
    cnt = 0, jw = 0;
    for (int i = 1; i <= n; i++) {
      if ((a[i] >> (w - 1)) & 1)
        jw++;
      else
        cnt++;
    }
    f[w][jw] = min(f[w][jw], f[w - 1][0] + cnt);
    for (int i = 1; i <= n; i++) {
      if ((a[i] >> (w - 1)) & 1)
        jw--;
      else
        cnt--;
      if ((a[i] >> (w - 1)) & 1)
        cnt++, jw++;
      else
        jw++;
      f[w][jw] = min(f[w][jw], f[w - 1][i] + cnt);
    }
  }
  printf("%d\n", f[60][0]);
  return 0;
}

```