CF2246D diss_quack and Array Game

你有一个 $n$ 个元素的数组 $a$。Alice 和 Bob 会在这个数组上玩一个游戏。在游戏开始前，Alice 可以选择一个下标 $i$，并将 $a_i$ 的值 $+1$。每次操作需要 $1$ 的代价。 Alice 操作结束后，游戏开始，Bob 先手。在 Bob 的回合，他可以选择两个下标 $i,j$ 并交换 $a_i,a_j$ 的值。注意，Bob 可以选择 $i=j$，此时无事发生。 在 Alice 的回合，如果 $a_1$ 是奇数，那么将 $a_1$ 减一，否则找到 $a$ 数组一个极长的前缀 $p$ 满足对于所有 $1 \le i \le p$，$a_i$ 都是偶数，并将所有 $1 \le i \le p$ 的 $a_i$ 都除以 $2$。Alice 每次操作需要 $1$ 的代价，且 Alice 必须操作。 当一个元素变成 $0$，他将被移出数组。例如，$a=[1,2,3]$，Alice 操作一次后数组 $a=[0,2,3]$，此时 $0$ 自动移除，数组 $a$ 变成 $[2,3]$。当 $a$ 变为空时游戏结束。 Alice 希望最小化她的代价，Bob 希望最大化 Alice 的代价。请你求出：两人在最优策略下 Alice 花费的代价。

本题单个测试点内有多个测试用例。第一行一个正整数 $t(1 \le t \le 10^4)$ 代表测试用例数量，对于每一个测试用例： - 第一行一个正整数 $n(1 \le n \le 10^5)$ 代表数组长度。 - 第二行 $n$ 个正整数 $a_1,a_2,...,a_n(1 \le a_i \le 10^5)$，代表数组元素。 单个测试点内的所有测试用例的 $n$ 之和不超过 $10^5$。

对于每一个测试用例，一行一个整数代表 Alice 在两人都使用最优策略下花费的代价。

在第一个测试用例中，Alice 初始不增加任何元素。第一步，Bob 选择 $i = j = 1$（不交换任何元素）。随后 Alice 将 $a_1$ 减去 1，数组变为 $[2, 3]$。 接下来 Bob 再次选择 $i = j = 1$。Alice 将 $a_1$ 除以 $2$，数组变为 $[1, 3]$。Bob 又选择 $i = j = 1$。Alice 对 $a_1$ 减 $1$，数组变为 $[3]$。此时 Bob 只能选择 $i = j = 1$，然后 Alice 再花费 $3$ 的代价使数组为空。Alice 总共花费代价为 $6$。可以证明这是最优策略下的结果。 在第二个测试用例中，Alice 同样初始不增加任何元素。可以证明，在最优策略下 Alice 会走 $5$ 步。