#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Fenwick {
    int n;
    vector<long long> bit;
    Fenwick(int a) {
        n = a;
        bit.resize(n + 1);
    }
    void update(int ind, long long val) {
        for (; ind <= n; ind += (ind & (-ind)))
            bit[ind] += val;
    }
    long long query(int ind) {
        long long res = 0;
        for (; ind; ind -= (ind & (-ind)))
            res += bit[ind];
        return res;
    }
};
long long solve(vector<int>& v, int l, int r) {
    long long res = 0;
    int n = v.size();
    Fenwick fwn(n);
    for (int i = l; i <= r; i++) {
        res += fwn.query(n) - fwn.query(v[i]);
        fwn.update(v[i], 1);
    }
    return res;
}
long long getMinSwap(vector<int> arr) {
    int n = arr.size();
    vector<int> cnt(n);
    for (int i = 0; i < n; ++i) {
        cnt[i] = __builtin_popcount(arr[i]);
    }
    vector<pair<int, int>> temp(n);
    for (int i = 0; i < n; ++i) {
        temp[i] = {arr[i], i};
    }
    sort(temp.begin(), temp.end());
    vector<int> val(n);
    int ct = 1;
    for (int i = 0; i < n; ++i) {
        val[temp[i].second] = ct++;
    }
    vector<int> v = val;
    bool chk = true;
    int ls = 0;
    for (int i = 1; i < n; ++i) {
        if (cnt[i] == cnt[i - 1]) {
            continue;
        } else {
            sort(v.begin() + ls, v.begin() + i);
            ls = i;
        }
    }
    sort(v.begin() + ls, v.end());
    for (int i = 0; i < n; ++i) {
        if (v[i] != (i + 1)) {
            chk = false;
            break;
        }
    }
    if (!chk) {
        return -1;
    } else {
        long long res = 0;
        ls = 0;
        for (int i = 1; i < n; ++i) {
            if (cnt[i] == cnt[i - 1]) {
                continue;
            } else {
                res += solve(val, ls, i - 1);
                ls = i;
            }
        }
        res += solve(val, ls, n - 1);
        return res;
    }
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
long long anser(vector<int>& arr, int i, vector<long long>& dp) {
      if (i >= arr.size()) {
        return -1;
    }
    if (dp[i] != -1) {
        return dp[i];
    }
    int ans=anser(arr,i+1,dp);
    return max(ans,max(ans|arr[i],arr[i]));
}
long long answer(vector<int>& arr) {
    int n = arr.size();
    vector<long long> dp(n, -1);
    return anser(arr, 0, dp);
}

#include <iostream>
#include <vector>
using namespace std;
pair<int, int> urgent(const vector<int>& arr, int n) {
    vector<int> freq(n + 1, 0);
    int duplicate = -1, missing = -1;
    for (int i = 0; i < n; i++) {
        freq[arr[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        if (freq[i] == 0) {
            missing = i;
        } else if (freq[i] > 1) {
            duplicate = i;
        }
    }
    if (duplicate != -1 && missing != -1) {
        return {duplicate, missing};
    } else {
        return {-1, -1};
    }
}