设技能 $i$ 的学生人数为 $\text{cnt}_i$，不同技能的种类数为 $\text{diff}$。那么第一队的大小不能超过 $\text{diff}$，第二队的大小不能超过 $\text{maxcnt} = \max(\text{cnt}_1, \text{cnt}_2, \dots, \text{cnt}_n)$。因此答案不会超过这两个值的最小值。

此外，我们考虑拥有最大人数 $\text{maxcnt}$ 的那个技能。这里有两种情况：

• 如果该技能的所有学生都进入第二队，那么两队的大小分别不超过 $\text{diff} - 1$ 和 $\text{maxcnt}$。
• 否则，至少有一名该技能的学生进入第一队，那么两队的大小分别不超过 $\text{diff}$ 和 $\text{maxcnt} - 1$。

所以答案为：

$$\max\big(\min(\text{diff} - 1,\ \text{maxcnt}),\ \min(\text{diff},\ \text{maxcnt} - 1)\big) $$

时间复杂度：$O(n)$。

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> cnt(n + 1);
		for (int i = 0; i < n; ++i) {
			int x;
			cin >> x;
			++cnt[x];
		}
		int mx = *max_element(cnt.begin(), cnt.end());
		int diff = n + 1 - count(cnt.begin(), cnt.end(), 0);
		cout << max(min(mx - 1, diff), min(mx, diff - 1)) << endl;
	}
	
	return 0;
}