CF1515D Phoenix and Socks

为了满足他对配对袜子的热爱，Phoenix 带着他的 $n$ 只袜子（$n$ 是偶数）来到了袜子店。他的每只袜子都有一个颜色 $c_i$，并且是左袜或右袜。 Phoenix 可以花 1 美元让袜子店进行以下任意一种操作： - 将一只袜子的颜色改为任意颜色 $c'$（$1 \le c' \le n$） - 将一只左袜变成右袜 - 将一只右袜变成左袜 袜子店可以对每只袜子进行任意次数的上述操作。注意，将左袜变成右袜或右袜变成左袜时，袜子的颜色不会改变。 一对匹配的袜子是指一只左袜和一只右袜且颜色相同。Phoenix 想知道，最少需要花费多少美元，才能让 $n/2$ 对袜子配对成功？每只袜子必须恰好属于一对匹配的袜子。

输入包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 1000$）——表示测试用例的数量。 每个测试用例的第一行包含三个整数 $n$、$l$ 和 $r$（$2 \le n \le 2 \cdot 10^5$，$n$ 为偶数，$0 \le l, r \le n$，$l + r = n$）——袜子的总数、左袜的数量和右袜的数量。 接下来一行包含 $n$ 个整数 $c_i$（$1 \le c_i \le n$）——表示袜子的颜色。前 $l$ 个袜子是左袜，后 $r$ 个袜子是右袜。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示 Phoenix 使 $n/2$ 对袜子配对所需的最小花费。每只袜子必须恰好属于一对匹配的袜子。

在第一个测试用例中，Phoenix 可以花费 $2$ 美元： - 将第 $1$ 只袜子的颜色改为 $2$ - 将第 $3$ 只袜子的颜色改为 $2$ 现在有 $3$ 对匹配的袜子。例如，$(1, 4)$、$(2, 5)$ 和 $(3, 6)$ 都是匹配对。 在第二个测试用例中，Phoenix 可以花费 $3$ 美元： - 将第 $6$ 只袜子从右袜变成左袜 - 将第 $3$ 只袜子的颜色改为 $1$ - 将第 $4$ 只袜子的颜色改为 $1$ 现在有 $3$ 对匹配的袜子。例如，$(1, 3)$、$(2, 4)$ 和 $(5, 6)$ 都是匹配对。 由 ChatGPT 4.1 翻译