CF1626D Martial Arts Tournament

Monocarp 计划举办一场武术锦标赛。比赛将根据体重分为三个组别：轻量级、中量级和重量级。每个组别的冠军将通过单败淘汰制决出。 具体来说，这意味着每个组别的参赛人数都必须是 $2$ 的幂次方，并且每个组别都必须至少有一名参赛者。 目前已有 $n$ 名选手报名参赛，第 $i$ 名选手的体重为 $a_i$。为了将选手分组，Monocarp 将设定两个整数体重界限 $x$ 和 $y$（$x < y$）。 所有体重严格小于 $x$ 的选手将被分为轻量级；所有体重大于等于 $y$ 的选手将被分为重量级；剩下的选手将被分为中量级。 有可能分组后某些组别的参赛人数不是 $2$ 的幂次方，也可能出现某些组别为空。为了解决这些问题，Monocarp 可以为每个组别邀请任意数量的额外选手。 注意，Monocarp 不能剔除已经报名的 $n$ 名选手。 然而，他希望邀请的额外选手数量尽可能少。请帮助 Monocarp 选择 $x$ 和 $y$，使得所需邀请的额外选手总数最小，并输出该最小值。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示已报名的选手人数。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$），表示每位已报名选手的体重。 所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示在选择体重界限 $x$ 和 $y$ 后，Monocarp 需要邀请的最少额外选手数量。

在第一个样例中，Monocarp 可以选择 $x=2$ 和 $y=3$。轻量级、中量级和重量级组别分别有 $2$、$1$ 和 $1$ 名选手，均为 $2$ 的幂次方，因此不需要额外邀请选手。 在第二个样例中，无论如何选择 $x$ 和 $y$，总会有一个组别有 $1$ 名选手，其余组别为空。因此，Monocarp 需要分别为其余两个组别各邀请 $1$ 名选手。 在第三个样例中，Monocarp 可以选择 $x=1$ 和 $y=2$。轻量级组别有 $0$ 人，中量级和重量级组别各有 $3$ 人，因此每个空组别都需要补充一名选手。 在第四个样例中，Monocarp 可以选择 $x=8$ 和 $y=9$。轻量级组别有 $8$ 人，中量级和重量级组别都为空，因此中量级和重量级组别各需要补充一名选手。 由 ChatGPT 4.1 翻译