#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
  uniform_int_distribution<long long> uid(l, r);
  return uid(rng);
}
const int N = 1e5 + 5;
const int LOGN = 63;
long long a[N], b[N];
int dp[LOGN][N];
long long pre0[N], pre1[N];
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  long long maxi = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    maxi = max(maxi, a[i]);
  }
  for (int i = 1; i <= n; i++) {
    a[i] = maxi - a[i];
  }
  vector<int> indexes;
  for (int i = 0; i <= LOGN - 1; i++) {
    for (int j = 0; j <= n; j++) {
      dp[i][j] = 1e9;
    }
  }
  dp[0][0] = 0;
  for (int i = 1; i <= n; i++) {
    indexes.push_back(i);
  }
  for (int b = 0; b < LOGN; b++) {
    if (b != 0) {
      vector<int> temp;
      for (int x : indexes) {
        if (!((a[x] >> (b - 1)) & 1)) temp.push_back(x);
      }
      for (int x : indexes) {
        if (((a[x] >> (b - 1)) & 1)) temp.push_back(x);
      }
      indexes = temp;
    }
    pre0[0] = pre1[0] = 0;
    int c = 0;
    for (int x : indexes) {
      c++;
      pre0[c] = pre0[c - 1];
      pre1[c] = pre1[c - 1];
      if ((a[x] >> b) & 1)
        pre1[c]++;
      else
        pre0[c]++;
    }
    for (int i = 0; i <= n; i++) {
      if (dp[b][i] == 1e9) continue;
      for (int bk = 0; bk < 2; bk++) {
        int carry, ones;
        if (bk == 0) {
          ones = pre0[n] - pre0[n - i] + pre1[n - i];
          carry = pre1[n] - pre1[n - i];
        } else {
          ones = pre0[n - i] + pre1[n] - pre1[n - i];
          carry = n - pre0[n - i];
        }
        dp[b + 1][carry] = min(dp[b + 1][carry], dp[b][i] + ones);
      }
    }
  }
  cout << dp[LOGN - 1][0];
  return 0;
}

### Prompt

Please create a solution in CPP 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;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
  uniform_int_distribution<long long> uid(l, r);
  return uid(rng);
}
const int N = 1e5 + 5;
const int LOGN = 63;
long long a[N], b[N];
int dp[LOGN][N];
long long pre0[N], pre1[N];
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  long long maxi = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    maxi = max(maxi, a[i]);
  }
  for (int i = 1; i <= n; i++) {
    a[i] = maxi - a[i];
  }
  vector<int> indexes;
  for (int i = 0; i <= LOGN - 1; i++) {
    for (int j = 0; j <= n; j++) {
      dp[i][j] = 1e9;
    }
  }
  dp[0][0] = 0;
  for (int i = 1; i <= n; i++) {
    indexes.push_back(i);
  }
  for (int b = 0; b < LOGN; b++) {
    if (b != 0) {
      vector<int> temp;
      for (int x : indexes) {
        if (!((a[x] >> (b - 1)) & 1)) temp.push_back(x);
      }
      for (int x : indexes) {
        if (((a[x] >> (b - 1)) & 1)) temp.push_back(x);
      }
      indexes = temp;
    }
    pre0[0] = pre1[0] = 0;
    int c = 0;
    for (int x : indexes) {
      c++;
      pre0[c] = pre0[c - 1];
      pre1[c] = pre1[c - 1];
      if ((a[x] >> b) & 1)
        pre1[c]++;
      else
        pre0[c]++;
    }
    for (int i = 0; i <= n; i++) {
      if (dp[b][i] == 1e9) continue;
      for (int bk = 0; bk < 2; bk++) {
        int carry, ones;
        if (bk == 0) {
          ones = pre0[n] - pre0[n - i] + pre1[n - i];
          carry = pre1[n] - pre1[n - i];
        } else {
          ones = pre0[n - i] + pre1[n] - pre1[n - i];
          carry = n - pre0[n - i];
        }
        dp[b + 1][carry] = min(dp[b + 1][carry], dp[b][i] + ones);
      }
    }
  }
  cout << dp[LOGN - 1][0];
  return 0;
}

```