#include <bits/stdc++.h>
using namespace std;
const int N = 100010, LOG = 60;
int n;
long long arr[N], mx;
int cnt[N], cnt2[N];
vector<pair<bool, int> > cur[N];
vector<pair<long long, int> > v;
int dp[LOG + 1][N];
int idx[N][LOG + 1];
int sum1[N], sum2[N], mx1[N], mx2[N];
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%lld", arr + i);
    mx = max(mx, arr[i]);
  }
  for (int i = 0; i < n; i++) arr[i] = mx - arr[i];
  for (int i = 0; i < LOG; i++) {
    v.clear();
    for (int j = 0; j < n; j++) {
      v.push_back(make_pair((arr[j] & (((long long)1 << (i + 1)) - 1)), j));
    }
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    cur[i].resize((int)v.size());
    for (int j = 0; j < (int)v.size(); j++) {
      cur[i][j].first = (((v[j].first >> i) & 1) == 1);
      cur[i][j].second = v[j].second;
      idx[cur[i][j].second][i + 1] = j;
    }
  }
  int tmp1, tmp2, tmp3, tmp4;
  for (int i = LOG; i >= 0; i--) {
    memset(sum1, 0, sizeof(sum1));
    memset(sum2, 0, sizeof(sum2));
    memset(mx1, 0, sizeof(mx1));
    memset(mx2, 0, sizeof(mx2));
    if (i != LOG) {
      for (int j = 0; j < (int)cur[i].size(); j++) {
        if (cur[i][j].first == 1) {
          sum1[idx[cur[i][j].second][i] + 1]++;
          mx1[idx[cur[i][j].second][i] + 1] = j + 1;
        } else {
          sum2[idx[cur[i][j].second][i] + 1]++;
          mx2[idx[cur[i][j].second][i] + 1] = j + 1;
        }
      }
      for (int j = 1; j <= (int)cur[i].size(); j++) {
        sum1[j] += sum1[j - 1];
        sum2[j] += sum2[j - 1];
        mx1[j] = max(mx1[j], mx1[j - 1]);
        mx2[j] = max(mx2[j], mx2[j - 1]);
      }
    }
    for (int j = 0; j <= (i == 0 ? 0 : (int)cur[i - 1].size()); j++) {
      if (i == LOG) {
        dp[i][j] = j;
        continue;
      }
      dp[i][j] = 1000000010;
      tmp1 = sum1[n] - sum1[j] + sum2[j];
      tmp2 = mx1[j];
      dp[i][j] = min(dp[i][j], dp[i + 1][tmp2] + tmp1);
      tmp1 = sum1[j] + (sum2[n] - sum2[j]);
      tmp2 = max(mx1[n], mx2[j]);
      dp[i][j] = min(dp[i][j], dp[i + 1][tmp2] + tmp1);
    }
  }
  cout << dp[0][0] << endl;
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

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 = 100010, LOG = 60;
int n;
long long arr[N], mx;
int cnt[N], cnt2[N];
vector<pair<bool, int> > cur[N];
vector<pair<long long, int> > v;
int dp[LOG + 1][N];
int idx[N][LOG + 1];
int sum1[N], sum2[N], mx1[N], mx2[N];
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%lld", arr + i);
    mx = max(mx, arr[i]);
  }
  for (int i = 0; i < n; i++) arr[i] = mx - arr[i];
  for (int i = 0; i < LOG; i++) {
    v.clear();
    for (int j = 0; j < n; j++) {
      v.push_back(make_pair((arr[j] & (((long long)1 << (i + 1)) - 1)), j));
    }
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    cur[i].resize((int)v.size());
    for (int j = 0; j < (int)v.size(); j++) {
      cur[i][j].first = (((v[j].first >> i) & 1) == 1);
      cur[i][j].second = v[j].second;
      idx[cur[i][j].second][i + 1] = j;
    }
  }
  int tmp1, tmp2, tmp3, tmp4;
  for (int i = LOG; i >= 0; i--) {
    memset(sum1, 0, sizeof(sum1));
    memset(sum2, 0, sizeof(sum2));
    memset(mx1, 0, sizeof(mx1));
    memset(mx2, 0, sizeof(mx2));
    if (i != LOG) {
      for (int j = 0; j < (int)cur[i].size(); j++) {
        if (cur[i][j].first == 1) {
          sum1[idx[cur[i][j].second][i] + 1]++;
          mx1[idx[cur[i][j].second][i] + 1] = j + 1;
        } else {
          sum2[idx[cur[i][j].second][i] + 1]++;
          mx2[idx[cur[i][j].second][i] + 1] = j + 1;
        }
      }
      for (int j = 1; j <= (int)cur[i].size(); j++) {
        sum1[j] += sum1[j - 1];
        sum2[j] += sum2[j - 1];
        mx1[j] = max(mx1[j], mx1[j - 1]);
        mx2[j] = max(mx2[j], mx2[j - 1]);
      }
    }
    for (int j = 0; j <= (i == 0 ? 0 : (int)cur[i - 1].size()); j++) {
      if (i == LOG) {
        dp[i][j] = j;
        continue;
      }
      dp[i][j] = 1000000010;
      tmp1 = sum1[n] - sum1[j] + sum2[j];
      tmp2 = mx1[j];
      dp[i][j] = min(dp[i][j], dp[i + 1][tmp2] + tmp1);
      tmp1 = sum1[j] + (sum2[n] - sum2[j]);
      tmp2 = max(mx1[n], mx2[j]);
      dp[i][j] = min(dp[i][j], dp[i + 1][tmp2] + tmp1);
    }
  }
  cout << dp[0][0] << endl;
  return 0;
}

```