nlogn approach for the awesome problem 2226C. Binary search the answer. ~~~~~ bool check_k(int a[], int n, int k) { vector leftover; vector 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;
}

} ~~~~~