← 返回题目列表

Codeforces · 1675/B

B. 使其增加

中文机器翻译题面 查看原题

给定 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$。您可以对它们执行以下操作:

- 选择任意元素 $$$a_i$$$ ($$$1 \le i \le n$$$) 并将其除以 $$$2$$$ (向下舍入)。换句话说,您可以将任何选定的元素 $$$a_i$$$ 替换为值 $$$\left \lfloor \frac{a_i}{2}\right\rfloor$$$ (其中 $$$\left \lfloor x \right\rfloor$$$ 是向下舍入实数 $$$x$$$)。

输出要使整数序列严格递增(即满足条件 $$$a_1 \lt a_2 \lt \dots \lt a_n$$$ 必须完成的最小操作数)。或者确定不可能获得这样的序列。请注意,元素不能交换。唯一可能的操作如上所述。

例如,让 $$$n = 3$$$ 并给出数字序列 $$$[3, 6, 5]$$$。然后对其执行两个操作就足够了:

- 写入数字 $$$\left \lfloor \frac{6}{2}\right\rfloor = 3$$$ 而不是数字 $$$a_2=6$$$ 并得到序列 $$$[3, 3, 5]$$$;
- 然后将 $$$a_1=3$$$ 替换为 $$$\left \lfloor \frac{3}{2}\right\rfloor = 1$$$ 并得到序列 $$$[1, 3, 5]$$$。

结果序列严格递增,因为 $$$1 \lt 3 \lt 5$$$。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 输入中测试用例的数量。

测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 30$$$)。

每个测试用例的第二行恰好包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2 \cdot 10^9$$$)。

输出

对于每个测试用例,在单独的行上打印一个数字 - 对序列执行的最小操作数,以使其严格递增。如果无法获得严格递增的序列,则打印“-1”。

示例

输入 #1

7
3
3 6 5
4
5 3 2 1
5
1 2 3 4 5
1
1000000000
4
2 8 7 5
5
8 26 5 21 10
2
5 14

输出 #1

2
-1
0
0
4
11
0

注意

语句中分析了第一个测试用例。

在第二个测试用例中,不可能获得严格递增的序列。

在第三个测试用例中,序列已经严格递增。