#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
long long pw(long long a, long long b) {
  long long ret = 1;
  long long mul = a;
  while (b > 0) {
    if (b & 1) ret = (ret * mul);
    mul = (mul * mul);
    b /= 2;
  }
  return ret;
}
long long to_int(string s) {
  long long ret = 0;
  for (int(i) = (0); (i) < (s.size()); (i)++) {
    ret += pw(10, s.size() - i - 1) * (long long)(s[i] - '0');
  }
  return ret;
}
const int MAXN = 1e5 + 15, lg = 6e1;
int n, cnt[lg], dp[lg][MAXN];
long long a[MAXN];
vector<pair<long long, long long> > sa[lg];
int main() {
  cin >> n;
  for (int(i) = (0); (i) < (n); (i)++) {
    cin >> a[i];
    long long x = a[i];
    for (int(t) = (0); (t) < (lg); (t)++) {
      if (x & 1) {
        cnt[lg - t - 1]++;
      }
      x /= 2;
    }
    long long cur = 0, cur1 = 1;
    for (int(t) = (0); (t) < (lg); (t)++) {
      cur = 2 * cur + 1;
      cur1 *= 2;
      sa[lg - t - 1].push_back({a[i] & cur, a[i] & cur1});
    }
  }
  for (int(i) = (0); (i) < (lg); (i)++)
    sort((sa[i]).begin(), (sa[i]).end()),
        reverse((sa[i]).begin(), (sa[i]).end());
  for (int(i) = (1); (i) < (n + 1); (i)++) dp[0][i] = n - i;
  for (int(i) = (1); (i) < (lg); (i)++)
    for (int(j) = (0); (j) < (MAXN); (j)++) dp[i][j] = MAXN * lg * 2;
  for (int(i) = (1); (i) < (lg); (i)++) {
    int c1 = 0, c0 = 0;
    for (int(j) = (0); (j) < ((n) * (i < lg - 1) + 1); (j)++) {
      dp[i][j] = min(dp[i - 1][c1] + c1 + n - cnt[i] - c0,
                     dp[i - 1][cnt[i] + c0] + cnt[i] - c1 + c0);
      if (j < (n) * (i < lg - 1)) {
        if (sa[i + 1][j].second)
          c1++;
        else
          c0++;
      }
    }
  }
  cout << dp[lg - 1][0] << "\n";
}

### Prompt

Construct a cpp code solution to the problem outlined:

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;
#pragma GCC optimize("Ofast")
long long pw(long long a, long long b) {
  long long ret = 1;
  long long mul = a;
  while (b > 0) {
    if (b & 1) ret = (ret * mul);
    mul = (mul * mul);
    b /= 2;
  }
  return ret;
}
long long to_int(string s) {
  long long ret = 0;
  for (int(i) = (0); (i) < (s.size()); (i)++) {
    ret += pw(10, s.size() - i - 1) * (long long)(s[i] - '0');
  }
  return ret;
}
const int MAXN = 1e5 + 15, lg = 6e1;
int n, cnt[lg], dp[lg][MAXN];
long long a[MAXN];
vector<pair<long long, long long> > sa[lg];
int main() {
  cin >> n;
  for (int(i) = (0); (i) < (n); (i)++) {
    cin >> a[i];
    long long x = a[i];
    for (int(t) = (0); (t) < (lg); (t)++) {
      if (x & 1) {
        cnt[lg - t - 1]++;
      }
      x /= 2;
    }
    long long cur = 0, cur1 = 1;
    for (int(t) = (0); (t) < (lg); (t)++) {
      cur = 2 * cur + 1;
      cur1 *= 2;
      sa[lg - t - 1].push_back({a[i] & cur, a[i] & cur1});
    }
  }
  for (int(i) = (0); (i) < (lg); (i)++)
    sort((sa[i]).begin(), (sa[i]).end()),
        reverse((sa[i]).begin(), (sa[i]).end());
  for (int(i) = (1); (i) < (n + 1); (i)++) dp[0][i] = n - i;
  for (int(i) = (1); (i) < (lg); (i)++)
    for (int(j) = (0); (j) < (MAXN); (j)++) dp[i][j] = MAXN * lg * 2;
  for (int(i) = (1); (i) < (lg); (i)++) {
    int c1 = 0, c0 = 0;
    for (int(j) = (0); (j) < ((n) * (i < lg - 1) + 1); (j)++) {
      dp[i][j] = min(dp[i - 1][c1] + c1 + n - cnt[i] - c0,
                     dp[i - 1][cnt[i] + c0] + cnt[i] - c1 + c0);
      if (j < (n) * (i < lg - 1)) {
        if (sa[i + 1][j].second)
          c1++;
        else
          c0++;
      }
    }
  }
  cout << dp[lg - 1][0] << "\n";
}

```