CF1956B.Nene and the Card Game

你和 Nene 正在玩一款纸牌游戏。游戏使用一副包含 $2n$ 张牌的牌堆，每张牌上写有一个从 $1$ 到 $n$ 的整数，并且每个整数 $1$ 到 $n$ 恰好各出现 $2$ 次。此外，桌面上有一个区域用于放置打出的牌（初始时桌面为空）。

游戏开始时，这 $2n$ 张牌被分配给你和 Nene，每人各获得 $n$ 张牌。

接下来，你和 Nene 轮流进行 $2n$ 个回合，也就是说每人各进行 $n$ 次操作，由你先手。每一回合：

• 当前玩家从自己手中选择一张牌，假设牌上的数字为 $x$。
• 如果桌面上已经有一张数字为 $x$ 的牌，则当前玩家获得 $1$ 分，否则不得分。然后，他将这张数字为 $x$ 的牌放到桌面上。

注意，所有回合都是公开进行的：每位玩家在任何时刻都能看到桌面上的所有牌。

Nene 非常聪明，她总是以最优策略选择出牌，以使自己在游戏结束（$2n$ 回合后）获得的分数最大。如果有多种最优选择，她会选择能让你最终得分最少的那种。

更正式地说，Nene 总是优先最大化自己的最终得分，其次最小化你的最终得分。

假设牌已经分配完毕，你手中的牌上的数字为 $a_1, a_2, \ldots, a_n$。请问如果你也采取最优策略，你最多能获得多少分？

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示你和 Nene 各自手中的牌数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示你手中每张牌上的数字。保证每个整数 $1$ 到 $n$ 在序列 $a_1, a_2, \ldots, a_n$ 中最多出现 $2$ 次。

保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示你在采取最优策略时最多能获得的分数。

在第一个测试用例中，你手中的牌上的数字为 $1$、$1$、$2$ 和 $3$。Nene 手中的牌上的数字为 $2$、$3$、$4$ 和 $4$。游戏过程可能如下：

1. 你选择一张数字为 $1$ 的牌并放到桌面上。
2. Nene 选择一张数字为 $4$ 的牌并放到桌面上。
3. 你选择另一张数字为 $1$ 的牌，获得 $1$ 分，并将其放到桌面上。
4. Nene 选择另一张数字为 $4$ 的牌，获得 $1$ 分，并将其放到桌面上。
5. 你选择数字为 $2$ 的牌并放到桌面上。
6. Nene 选择数字为 $2$ 的牌，获得 $1$ 分，并将其放到桌面上。
7. 你选择数字为 $3$ 的牌并放到桌面上。
8. Nene 选择数字为 $3$ 的牌，获得 $1$ 分，并将其放到桌面上。

最终，你获得 $1$ 分，Nene 获得 $3$ 分。可以证明，如果 Nene 采取最优策略，你无法获得超过 $1$ 分，因此答案为 $1$。

在第二个测试用例中，如果双方都采取最优策略，你可以获得 $2$ 分，Nene 获得 $6$ 分。

由 ChatGPT 4.1 翻译