#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
void ckmin(T &a, U b) {
  if (a > b) a = b;
}
template <class T, class U>
void ckmax(T &a, U b) {
  if (a < b) a = b;
}
int N;
long long arr[100013];
int dp[2][100013];
int ans;
vector<pair<long long, long long> > nums;
int getbit(int x, int b) { return (arr[x] & (1ll << b)) ? 1 : 0; }
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> N;
  for (auto i = (0); i < (N); i++) {
    cin >> arr[i];
  }
  sort(arr, arr + N);
  for (auto i = (0); i < (N); i++) {
    arr[i] = arr[N - 1] - arr[i];
    arr[i] *= 2;
    cerr << arr[i] << ' ';
  }
  cerr << endl;
  for (auto i = (0); i < (N); i++) {
    nums.push_back({0, i});
  }
  for (auto i = (0); i < (N + 1); i++) {
    dp[0][i] = 1000000007;
    dp[1][i] = 1000000007;
  }
  dp[0][N] = 0;
  for (auto i = (1); i < (61); i++) {
    for (auto j = (0); j < (N + 1); j++) {
      dp[i & 1][j] = 1000000007;
    }
    vector<pair<long long, long long> > cur;
    for (auto j = (0); j < (N); j++) {
      cur.push_back({(arr[j] & ((2ll << i) - 1)), j});
    }
    sort((cur).begin(), (cur).end());
    int to = N, sum = 0;
    for (auto j = (0); j < (N); j++) sum += getbit(j, i);
    for (auto j = (N + 1) - 1; j >= (0); j--) {
      if (j != N) {
        int ind = nums[j].second;
        if (getbit(ind, i)) {
          to--;
          sum--;
        } else {
          sum++;
        }
        if (j != 0 && nums[j].first == nums[j - 1].first) continue;
      }
      ckmin(dp[i & 1][to], dp[(i & 1) ^ 1][j] + sum);
    }
    sum = 0;
    to = N;
    for (auto j = (0); j < (N); j++) sum += (getbit(j, i) ^ 1);
    for (auto j = (0); j < (N); j++)
      if (getbit(j, i)) to--;
    for (auto j = (N + 1) - 1; j >= (0); j--) {
      if (j != N) {
        int ind = nums[j].second;
        if (!getbit(ind, i)) {
          to--;
          sum--;
        } else {
          sum++;
        }
        if (j != 0 && nums[j].first == nums[j - 1].first) continue;
      }
      ckmin(dp[i & 1][to], dp[(i & 1) ^ 1][j] + sum);
    }
    nums = cur;
  }
  ans = dp[0][N];
  cout << ans << '\n';
  return 0;
}

### 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;
template <class T, class U>
void ckmin(T &a, U b) {
  if (a > b) a = b;
}
template <class T, class U>
void ckmax(T &a, U b) {
  if (a < b) a = b;
}
int N;
long long arr[100013];
int dp[2][100013];
int ans;
vector<pair<long long, long long> > nums;
int getbit(int x, int b) { return (arr[x] & (1ll << b)) ? 1 : 0; }
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> N;
  for (auto i = (0); i < (N); i++) {
    cin >> arr[i];
  }
  sort(arr, arr + N);
  for (auto i = (0); i < (N); i++) {
    arr[i] = arr[N - 1] - arr[i];
    arr[i] *= 2;
    cerr << arr[i] << ' ';
  }
  cerr << endl;
  for (auto i = (0); i < (N); i++) {
    nums.push_back({0, i});
  }
  for (auto i = (0); i < (N + 1); i++) {
    dp[0][i] = 1000000007;
    dp[1][i] = 1000000007;
  }
  dp[0][N] = 0;
  for (auto i = (1); i < (61); i++) {
    for (auto j = (0); j < (N + 1); j++) {
      dp[i & 1][j] = 1000000007;
    }
    vector<pair<long long, long long> > cur;
    for (auto j = (0); j < (N); j++) {
      cur.push_back({(arr[j] & ((2ll << i) - 1)), j});
    }
    sort((cur).begin(), (cur).end());
    int to = N, sum = 0;
    for (auto j = (0); j < (N); j++) sum += getbit(j, i);
    for (auto j = (N + 1) - 1; j >= (0); j--) {
      if (j != N) {
        int ind = nums[j].second;
        if (getbit(ind, i)) {
          to--;
          sum--;
        } else {
          sum++;
        }
        if (j != 0 && nums[j].first == nums[j - 1].first) continue;
      }
      ckmin(dp[i & 1][to], dp[(i & 1) ^ 1][j] + sum);
    }
    sum = 0;
    to = N;
    for (auto j = (0); j < (N); j++) sum += (getbit(j, i) ^ 1);
    for (auto j = (0); j < (N); j++)
      if (getbit(j, i)) to--;
    for (auto j = (N + 1) - 1; j >= (0); j--) {
      if (j != N) {
        int ind = nums[j].second;
        if (!getbit(ind, i)) {
          to--;
          sum--;
        } else {
          sum++;
        }
        if (j != 0 && nums[j].first == nums[j - 1].first) continue;
      }
      ckmin(dp[i & 1][to], dp[(i & 1) ^ 1][j] + sum);
    }
    nums = cur;
  }
  ans = dp[0][N];
  cout << ans << '\n';
  return 0;
}

```