nlogn approach for the awesome problem 2226C. Binary search the answer.

bool check_k(int a[], int n, int k) {
    vector<int> leftover;
    vector<int> mex(k, 0);

    for (int i = 0; i < n; i++)
        if (a[i] < k && !mex[a[i]])
            mex[a[i]] = 1;
        else
            leftover.push_back(a[i]);

    int i = 0, j = 0;
    while (i < k && j < leftover.size()) {
        while (i < k && mex[i]) i++;

        if (i < k && leftover[j] > 2 * i) mex[i] = 1;
        j++;
    }
    while (i < k && mex[i]) i++;

    return i == k;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        int a[n];
        for (int& x : a) cin >> x;
        std::sort(a, a + n);

        int l = 1, r = n;
        while (l <= r) {
            int k = (l + r) / 2;
            bool res = check_k(a, n, k);

            if (res)
                l = k + 1;
            else
                r = k - 1;
        }

        cout << r << endl;
    }
}