我们先对 $a$ 排序，此时 $a_n$ 为最大值。

显然，如果 Bessie 什么都不做，排序所需的时间一定是 $a_n$。

不妨设 Bessie 刚开始选了 $x$ 个数给自己，我们考虑判断一个 $x$ 是否合法。

首先，对于一个 $x$，所有满足 $a_i < x$ 的数一定要交给帮手们。这是因为 Bessie 会在 $x$ 秒插入最小的数，此时比 $x$ 小的必须已经出现在最终序列中，不然无法保证正确性。注意，由于 Bessie 的优先级更高，所以恰好为 $x$ 的 $a_i$ 要交给 Bessie。

我们记录一个 $cnt$，表示 Bessie 选择了几个数给自己。显然，我们可以顺序枚举，如果遇到一个数满足 $a_i \geq sz$，就需要把这个数给 Bessie。其中 $sz$ 表示目前 Bessie 还剩余的数的数量。

按照上述方法模拟，我们最终得到的 $cnt$ 就是 Bessie 给自己选择的数有多少。一个合法的 $x$ 在模拟后一定满足 $cnt \leq x$。

由于花费 $a_n$ 秒排序一定有解，所以 $x$ 需要满足 $1 + 2 + \cdots + x \leq a_n$ 才可能更优，即 $x$ 的上界为 $\sqrt{a_n}$。

因此，我们可以直接枚举 $\sqrt{a_n}$ 以内的数作为 $x$，然后 $\mathcal{O}(n)$ 判断是否合法。这样我们就得到了一个 $\mathcal{O}(n\sqrt{V})$ 的做法，其中 $V$ 是值域。

这样是不足以通过的，我们需要优化。

注意到，$x$ 越大，对 Bessie 的要求就越低！因此，我们可以把枚举转化成二分答案。

使用二分答案，时间复杂度降为了 $\mathcal{O}(n\log_2(\sqrt{V}))$，足以通过。

参考代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
inline void write(int x){
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
    return;
}
int n, a[200005];
signed main(){
    int T = read();
    while(T--){
        n = read();
        for(int i = 1; i <= n; i++) a[i] = read();
        sort(a + 1, a + 1 + n);
        int l = 0, r = sqrt(a[n]) + 114514, ans = 4e18;
        while(l <= r){
            int mid = (l + r) >> 1, cnt = 0, sz = mid, base = 0;
            for(int i = 1; i <= n; i++) if(a[i] >= sz + base) cnt++, base += sz, sz--;
            if(cnt <= mid){
                ans = mid * (mid + 1ll) / 2ll;
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        write(min(a[n], ans)), putchar('\n');
    }
    return 0;
}