#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int N;
long long A[maxn], D[maxn];
int ord[60][maxn], psum[60][maxn], one[60];
int calc(int l, int r, int *psum) {
  if (l > r) return 0;
  return psum[r] - (l ? psum[l - 1] : 0);
}
int cc[60][maxn];
int dp(int b, int n) {
  if (b == 60) return n;
  int &ret = cc[b][n];
  if (ret != -1) return ret;
  ret = 1e9;
  int c11 = calc(N - n, N - 1, psum[b - 1]);
  int c10 = n - c11;
  int c01 = calc(0, N - n - 1, psum[b - 1]);
  int c00 = N - n - c01;
  ret = min(ret, dp(b + 1, c11) + c10 + c01);
  ret = min(ret, dp(b + 1, one[b] + c10) + c00 + c11);
  return ret;
}
int main() {
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &A[i]);
  }
  sort(A, A + N);
  for (int i = 0; i < N; i++) {
    D[i] = A[N - 1] - A[i];
  }
  int cnt = 0;
  for (int i = 0; i < N; i++)
    if (!(D[i] & 1)) ord[0][cnt++] = i;
  for (int i = 0; i < N; i++)
    if (D[i] & 1) ord[0][cnt++] = i, one[0]++;
  for (int i = 1; i < 60; i++) {
    cnt = 0;
    for (int j = 0; j < N; j++)
      if (!(D[ord[i - 1][j]] & (1LL << i))) ord[i][cnt++] = ord[i - 1][j];
    for (int j = 0; j < N; j++)
      if (D[ord[i - 1][j]] & (1LL << i))
        ord[i][cnt++] = ord[i - 1][j], one[i]++;
  }
  for (int i = 0; i < 60; i++) {
    for (int j = 0; j < N; j++) {
      psum[i][j] = (D[ord[i][j]] & (1LL << (i + 1))) ? 1 : 0;
      if (j) psum[i][j] += psum[i][j - 1];
    }
  }
  memset(cc, -1, sizeof(cc));
  printf("%d", min(dp(1, 0) + one[0], dp(1, one[0]) + N - one[0]));
}

### Prompt

Your challenge is to write 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 maxn = 100010;
int N;
long long A[maxn], D[maxn];
int ord[60][maxn], psum[60][maxn], one[60];
int calc(int l, int r, int *psum) {
  if (l > r) return 0;
  return psum[r] - (l ? psum[l - 1] : 0);
}
int cc[60][maxn];
int dp(int b, int n) {
  if (b == 60) return n;
  int &ret = cc[b][n];
  if (ret != -1) return ret;
  ret = 1e9;
  int c11 = calc(N - n, N - 1, psum[b - 1]);
  int c10 = n - c11;
  int c01 = calc(0, N - n - 1, psum[b - 1]);
  int c00 = N - n - c01;
  ret = min(ret, dp(b + 1, c11) + c10 + c01);
  ret = min(ret, dp(b + 1, one[b] + c10) + c00 + c11);
  return ret;
}
int main() {
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &A[i]);
  }
  sort(A, A + N);
  for (int i = 0; i < N; i++) {
    D[i] = A[N - 1] - A[i];
  }
  int cnt = 0;
  for (int i = 0; i < N; i++)
    if (!(D[i] & 1)) ord[0][cnt++] = i;
  for (int i = 0; i < N; i++)
    if (D[i] & 1) ord[0][cnt++] = i, one[0]++;
  for (int i = 1; i < 60; i++) {
    cnt = 0;
    for (int j = 0; j < N; j++)
      if (!(D[ord[i - 1][j]] & (1LL << i))) ord[i][cnt++] = ord[i - 1][j];
    for (int j = 0; j < N; j++)
      if (D[ord[i - 1][j]] & (1LL << i))
        ord[i][cnt++] = ord[i - 1][j], one[i]++;
  }
  for (int i = 0; i < 60; i++) {
    for (int j = 0; j < N; j++) {
      psum[i][j] = (D[ord[i][j]] & (1LL << (i + 1))) ? 1 : 0;
      if (j) psum[i][j] += psum[i][j - 1];
    }
  }
  memset(cc, -1, sizeof(cc));
  printf("%d", min(dp(1, 0) + one[0], dp(1, one[0]) + N - one[0]));
}

```