U710460 展馆挑战

蜗蜗来到了一座主题展馆。展馆内共有 $n$ 个尚未参观的展区，第 $i$ 个展区的等级为 $a_{i}$。 蜗蜗和哞哞要轮流参观展区，由蜗蜗先开始。每个展区只能被其中一人参观一次。 - 轮到蜗蜗时，她选择的展区等级必须严格大于她之前参观过的每一个展区。由于开始时没有参观记录，所以蜗蜗第一次可以选择任意展区。 - 轮到哞哞时，他可以选择任意一个尚未被参观的展区。 如果轮到某个人时，他无法选出符合要求的展区，参观挑战就会立刻结束。 蜗蜗希望自己参观的展区数量尽可能多，哞哞则希望这个数量尽可能少。两人都会按照自己的目标选择最优策略。 请你求出挑战结束时，蜗蜗一共会参观多少个展区。

第一行输入一个整数 $t$，表示测试用例的组数。 对于每组测试用例： 第一行输入一个整数 $n$，表示展区数量。 第二行输入 $n$ 个整数 $a_{1},a_{2},…,a_{n}$，表示每个展区的等级。

对于每组测试用例，输出一个整数，表示双方都采取最优策略时蜗蜗最终参观的展区数量。

**样例解释** 对于样例 $1$： 第一组数据中，蜗蜗可以先参观等级为 $1$ 的展区。无论哞哞接下来选择等级为 $2$ 还是 $3$ 的展区，蜗蜗都可以再选择另一个等级更高的展区。由于一共只有 $3$ 个展区，哞哞至少会参观其中一个，所以蜗蜗最终会参观 $2$ 个展区。 第二组数据中，所有展区的等级都是 $4$。蜗蜗参观第一个展区后，剩余展区的等级都没有严格变大，因此蜗蜗无法继续选择。答案为 $1$。 对于样例 $2$： 第一组数据中，蜗蜗可以先选择一个等级为 $1$ 的展区。哞哞在自己的回合只能参观一个展区，因此蜗蜗下一次仍然可以选择一个等级为 $2$ 展区。之后已经不存在等级严格大于 $2$ 的展区，所以答案为 $2$。 第二组数据中，蜗蜗可以先选择一个等级为 $1$ 的展区，并保证之后再选择一个等级为 $2$ 的展区。另一方面，哞哞可以在自己的第一个回合选择等级为 $3$ 的展区。这样蜗蜗最多只能参观 $2$ 个展区。因此答案为 $2$。 **数据范围** 对于 $10\%$ 的数据，保证所有测试用例的 $n$ 之和不超过 $20$。 对于 $100\%$ 的数据，保证 $1\le t\le500，1\le n\le5000，1\le a_{i}\le n$，且所有测试用例的 $n$ 之和不超过 $5000$。