#include <bits/stdc++.h>
#define endl '\n'
#define ll long long int
#define pb push_back
#define pf push_front
#define F first
#define S second
const ll MOD = 1e9 + 7;

using namespace std;

ll solve(int n, int k, int m) {
    vector<vector<ll>> dp(k + 1, vector<ll>(m, 0));
    dp[0][0] = 1;

    for (ll num = 0; num < n; num++) {
        vector<vector<ll>> new_dp = dp;
        for (ll size = 1; size <= k; size++) {
            for (ll rem = 0; rem < m; rem++) {
                ll new_rem = (rem + num) % m;
                new_dp[size][new_rem] = (new_dp[size][new_rem] + dp[size - 1][rem]) % MOD;
            }
        }
        dp = new_dp;
    }

    return dp[k][0];
}

#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
public:
    vector<int> parent, rank, size;

    UnionFind(int n) : parent(n), rank(n, 1), size(n, 1) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            } else {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
                rank[rootX]++;
            }
        }
    }

    int getSize(int x) {
        int rootX = find(x);
        return size[rootX];
    }
};

long long countPairs(int n, int k, vector<int>& u, vector<int>& v) {
    UnionFind uf(n);
    for (int i = 0; i < k; ++i) {
        uf.unionSets(u[i], v[i]);
    }
    long long totalPairs = (long long)n * (n - 1) / 2;
    vector<bool> visited(n, false);
    for (int i = 0; i < n; ++i) {
        int root = uf.find(i);
        if (!visited[root]) {
            visited[root] = true;
            int clusterSize = uf.getSize(i);
            if (clusterSize > 1) {
                totalPairs -= (long long)clusterSize * (clusterSize - 1) / 2;
            }
        }
    }

    return totalPairs;
}

#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};
    }
}