#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 50, M = 60;
int dp[M][N], n, m;
long long a[N], msk;
int b[M][N];
void chkmn(int &a, int b) {
  if (a > b) a = b;
}
int main() {
  cin >> n;
  long long mx = 0;
  for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), mx = max(mx, a[i]);
  for (int i = 1; i <= n; i++) a[i] = mx - a[i];
  while (mx) mx >>= 1, ++m;
  memset(dp, 0x3f, sizeof(dp));
  for (int t = 0; t <= m + 1; t++) {
    msk = (1ll << (t + 1)) - 1;
    for (int i = 1; i <= n; i++) b[t][i] = i;
    sort(b[t] + 1, b[t] + n + 1, [](const int &i, const int &j) {
      return (a[i] & msk) < (a[j] & msk);
    });
    if (t == 0) {
      int c = 0;
      for (int i = 1; i <= n; i++) c += a[i] >> t & 1;
      dp[0][c] = n - c, dp[0][0] = c;
      continue;
    }
    int c = 0;
    for (int i = 1; i <= n; i++) c += a[i] >> t & 1;
    for (int i = 0, k = 0; i <= n; i++) {
      chkmn(dp[t][k], dp[t - 1][i] + c);
      if (a[b[t - 1][n - i]] >> t & 1)
        c -= 1, ++k;
      else
        c += 1;
    }
    c = 0;
    for (int i = 1; i <= n; i++) c += a[i] >> t & 1;
    for (int i = 0, k = c; i <= n; i++) {
      chkmn(dp[t][k], dp[t - 1][i] + n - c);
      if (a[b[t - 1][n - i]] >> t & 1)
        c -= 1;
      else
        c += 1, ++k;
    }
  }
  cout << dp[m + 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;
const int N = 1e5 + 50, M = 60;
int dp[M][N], n, m;
long long a[N], msk;
int b[M][N];
void chkmn(int &a, int b) {
  if (a > b) a = b;
}
int main() {
  cin >> n;
  long long mx = 0;
  for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), mx = max(mx, a[i]);
  for (int i = 1; i <= n; i++) a[i] = mx - a[i];
  while (mx) mx >>= 1, ++m;
  memset(dp, 0x3f, sizeof(dp));
  for (int t = 0; t <= m + 1; t++) {
    msk = (1ll << (t + 1)) - 1;
    for (int i = 1; i <= n; i++) b[t][i] = i;
    sort(b[t] + 1, b[t] + n + 1, [](const int &i, const int &j) {
      return (a[i] & msk) < (a[j] & msk);
    });
    if (t == 0) {
      int c = 0;
      for (int i = 1; i <= n; i++) c += a[i] >> t & 1;
      dp[0][c] = n - c, dp[0][0] = c;
      continue;
    }
    int c = 0;
    for (int i = 1; i <= n; i++) c += a[i] >> t & 1;
    for (int i = 0, k = 0; i <= n; i++) {
      chkmn(dp[t][k], dp[t - 1][i] + c);
      if (a[b[t - 1][n - i]] >> t & 1)
        c -= 1, ++k;
      else
        c += 1;
    }
    c = 0;
    for (int i = 1; i <= n; i++) c += a[i] >> t & 1;
    for (int i = 0, k = c; i <= n; i++) {
      chkmn(dp[t][k], dp[t - 1][i] + n - c);
      if (a[b[t - 1][n - i]] >> t & 1)
        c -= 1;
      else
        c += 1, ++k;
    }
  }
  cout << dp[m + 1][0];
  return 0;
}

```