#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9, Lg = 62, second = 2;
int n, dp[Lg][N], Rank[Lg][N], Rnk[Lg][N];
long long mx, a[N];
pair<int, int> res[Lg][N][second];
pair<long long, int> b[N];
void Fupdate(int lg, int bit) {
  for (int i = 1; i < n + 1; i++) {
    res[lg][0][bit].first += (((0 < (a[i] & (1ll << lg))) + bit) & 1);
    if ((0 < (a[i] & (1ll << lg))) + bit == 2) {
      res[lg][0][bit].second = max(res[lg][0][bit].second, Rank[lg][i]);
    }
  }
  dp[lg + 1][res[lg][0][bit].second] = min(dp[lg + 1][res[lg][0][bit].second],
                                           dp[lg][0] + res[lg][0][bit].first);
}
void update(int x, int lg, int bit) {
  long long u = a[Rnk[lg][x]];
  res[lg][x][bit] = res[lg][x - 1][bit];
  if (2 <= (0 < (u & (1ll << lg))) + bit + 1) {
    res[lg][x][bit].second = max(res[lg][x][bit].second, Rank[lg][Rnk[lg][x]]);
  }
  if (((0 < (u & (1ll << lg))) + bit + 1) & 1) res[lg][x][bit].first += 2;
  res[lg][x][bit].first--;
  dp[lg + 1][res[lg][x][bit].second] = min(dp[lg + 1][res[lg][x][bit].second],
                                           dp[lg][x] + res[lg][x][bit].first);
}
int main() {
  cin >> n;
  for (int i = 1; i < n + 1; i++) {
    cin >> a[i];
    mx = max(mx, a[i]);
  }
  for (int i = 1; i < n + 1; i++) a[i] = mx - a[i];
  for (int i = 0; i < Lg - 1; i++) {
    for (int j = 1; j < n + 1; j++)
      b[j] = make_pair(a[j] % (1ll << (i + 1)), j);
    sort(b + 1, b + 1 + n);
    reverse(b + 1, b + 1 + n);
    for (int j = 1; j < n + 1; j++) {
      Rank[i][b[j].second] = j;
      Rnk[i + 1][j] = b[j].second;
    }
  }
  for (int j = 0; j < Lg; j++)
    for (int i = 0; i < n + 1; i++) dp[j][i] = N * Lg;
  dp[0][0] = 0;
  for (int i = 0; i < Lg - 1; i++) {
    Fupdate(i, 0);
    Fupdate(i, 1);
    for (int j = 1; j < n + 1; j++) {
      update(j, i, 0);
      update(j, i, 1);
    }
  }
  cout << dp[Lg - 2][0] << '\n';
}

### 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 N = 1e5 + 9, Lg = 62, second = 2;
int n, dp[Lg][N], Rank[Lg][N], Rnk[Lg][N];
long long mx, a[N];
pair<int, int> res[Lg][N][second];
pair<long long, int> b[N];
void Fupdate(int lg, int bit) {
  for (int i = 1; i < n + 1; i++) {
    res[lg][0][bit].first += (((0 < (a[i] & (1ll << lg))) + bit) & 1);
    if ((0 < (a[i] & (1ll << lg))) + bit == 2) {
      res[lg][0][bit].second = max(res[lg][0][bit].second, Rank[lg][i]);
    }
  }
  dp[lg + 1][res[lg][0][bit].second] = min(dp[lg + 1][res[lg][0][bit].second],
                                           dp[lg][0] + res[lg][0][bit].first);
}
void update(int x, int lg, int bit) {
  long long u = a[Rnk[lg][x]];
  res[lg][x][bit] = res[lg][x - 1][bit];
  if (2 <= (0 < (u & (1ll << lg))) + bit + 1) {
    res[lg][x][bit].second = max(res[lg][x][bit].second, Rank[lg][Rnk[lg][x]]);
  }
  if (((0 < (u & (1ll << lg))) + bit + 1) & 1) res[lg][x][bit].first += 2;
  res[lg][x][bit].first--;
  dp[lg + 1][res[lg][x][bit].second] = min(dp[lg + 1][res[lg][x][bit].second],
                                           dp[lg][x] + res[lg][x][bit].first);
}
int main() {
  cin >> n;
  for (int i = 1; i < n + 1; i++) {
    cin >> a[i];
    mx = max(mx, a[i]);
  }
  for (int i = 1; i < n + 1; i++) a[i] = mx - a[i];
  for (int i = 0; i < Lg - 1; i++) {
    for (int j = 1; j < n + 1; j++)
      b[j] = make_pair(a[j] % (1ll << (i + 1)), j);
    sort(b + 1, b + 1 + n);
    reverse(b + 1, b + 1 + n);
    for (int j = 1; j < n + 1; j++) {
      Rank[i][b[j].second] = j;
      Rnk[i + 1][j] = b[j].second;
    }
  }
  for (int j = 0; j < Lg; j++)
    for (int i = 0; i < n + 1; i++) dp[j][i] = N * Lg;
  dp[0][0] = 0;
  for (int i = 0; i < Lg - 1; i++) {
    Fupdate(i, 0);
    Fupdate(i, 1);
    for (int j = 1; j < n + 1; j++) {
      update(j, i, 0);
      update(j, i, 1);
    }
  }
  cout << dp[Lg - 2][0] << '\n';
}

```