#include <bits/stdc++.h>
const int md = 1e9 + 7;
const long long inf = 1e18;
const int OO = 0;
const int OOO = 1;
using namespace std;
int n;
long long a[100005];
int dp[60][100005];
long long b[60][100005];
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  long long M = *max_element(a, a + n);
  for (int i = 0; i < n; i++) a[i] = M - a[i];
  for (int i = 0; i < 60; i++) {
    for (int j = 0; j < n; j++) b[i][j] = a[j];
    sort(b[i], b[i] + n, [i](long long aa, long long bb) {
      return (aa % (1LL << (long long)i)) < (bb % (1LL << (long long)i));
    });
  }
  int cnt = 0;
  for (int i = 0; i < n; i++) cnt += b[1][i] & 1;
  for (int j = 0; j <= n; j++) dp[1][j] = md;
  dp[1][0] = min(dp[1][0], cnt);
  dp[1][cnt] = min(dp[1][cnt], n - cnt);
  for (int i = 1; i + 1 < 60; i++) {
    if (OO) {
      cout << "starting " << i << '\n';
      cout << "dp: ";
      for (int j = 0; j <= n; j++) cout << dp[i][j] << " ";
      cout << '\n';
    }
    for (int j = 0; j <= n; j++) dp[i + 1][j] = md;
    int in[2], out[2];
    long long P = i;
    if (OO) cout << "put 0\n";
    in[0] = in[1] = out[0] = out[1] = 0;
    for (int j = 0; j < n; j++) out[b[i][j] >> P & 1]++;
    for (int j = 0; j <= n; j++) {
      int c = in[1];
      if (OO) {
        cout << "from " << i << " " << j << " to " << i + 1 << " " << c
             << " with addition of " << in[0] + out[1] << '\n';
      }
      dp[i + 1][c] = min(dp[i + 1][c], dp[i][j] + in[0] + out[1]);
      if (j == n) break;
      long long v = b[i][n - 1 - j];
      if (OO) cout << "upd " << v << " " << (v >> P & 1) << '\n';
      out[v >> P & 1]--;
      in[v >> P & 1]++;
    }
    if (OO) cout << "put 1\n";
    in[0] = in[1] = out[0] = out[1] = 0;
    for (int j = 0; j < n; j++) out[b[i][j] >> P & 1]++;
    for (int j = 0; j <= n; j++) {
      int c = in[0] + in[1] + out[1];
      if (OO) {
        cout << "from " << i << " " << j << " to " << i + 1 << " " << c
             << " with addition of " << in[1] + out[0] << '\n';
      }
      dp[i + 1][c] = min(dp[i + 1][c], dp[i][j] + in[1] + out[0]);
      if (j == n) break;
      long long v = b[i][n - 1 - j];
      out[v >> P & 1]--;
      in[v >> P & 1]++;
    }
  }
  cout << dp[59][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>
const int md = 1e9 + 7;
const long long inf = 1e18;
const int OO = 0;
const int OOO = 1;
using namespace std;
int n;
long long a[100005];
int dp[60][100005];
long long b[60][100005];
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  long long M = *max_element(a, a + n);
  for (int i = 0; i < n; i++) a[i] = M - a[i];
  for (int i = 0; i < 60; i++) {
    for (int j = 0; j < n; j++) b[i][j] = a[j];
    sort(b[i], b[i] + n, [i](long long aa, long long bb) {
      return (aa % (1LL << (long long)i)) < (bb % (1LL << (long long)i));
    });
  }
  int cnt = 0;
  for (int i = 0; i < n; i++) cnt += b[1][i] & 1;
  for (int j = 0; j <= n; j++) dp[1][j] = md;
  dp[1][0] = min(dp[1][0], cnt);
  dp[1][cnt] = min(dp[1][cnt], n - cnt);
  for (int i = 1; i + 1 < 60; i++) {
    if (OO) {
      cout << "starting " << i << '\n';
      cout << "dp: ";
      for (int j = 0; j <= n; j++) cout << dp[i][j] << " ";
      cout << '\n';
    }
    for (int j = 0; j <= n; j++) dp[i + 1][j] = md;
    int in[2], out[2];
    long long P = i;
    if (OO) cout << "put 0\n";
    in[0] = in[1] = out[0] = out[1] = 0;
    for (int j = 0; j < n; j++) out[b[i][j] >> P & 1]++;
    for (int j = 0; j <= n; j++) {
      int c = in[1];
      if (OO) {
        cout << "from " << i << " " << j << " to " << i + 1 << " " << c
             << " with addition of " << in[0] + out[1] << '\n';
      }
      dp[i + 1][c] = min(dp[i + 1][c], dp[i][j] + in[0] + out[1]);
      if (j == n) break;
      long long v = b[i][n - 1 - j];
      if (OO) cout << "upd " << v << " " << (v >> P & 1) << '\n';
      out[v >> P & 1]--;
      in[v >> P & 1]++;
    }
    if (OO) cout << "put 1\n";
    in[0] = in[1] = out[0] = out[1] = 0;
    for (int j = 0; j < n; j++) out[b[i][j] >> P & 1]++;
    for (int j = 0; j <= n; j++) {
      int c = in[0] + in[1] + out[1];
      if (OO) {
        cout << "from " << i << " " << j << " to " << i + 1 << " " << c
             << " with addition of " << in[1] + out[0] << '\n';
      }
      dp[i + 1][c] = min(dp[i + 1][c], dp[i][j] + in[1] + out[0]);
      if (j == n) break;
      long long v = b[i][n - 1 - j];
      out[v >> P & 1]--;
      in[v >> P & 1]++;
    }
  }
  cout << dp[59][0] << '\n';
}

```