← 返回题目列表

Codeforces · 1883/E

E. 回头看

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

给定一个整数数组 $$$a_1, a_2, \ldots, a_n$$$。你需要用最少的操作次数使其不减。在一项操作中,您执行以下操作:

- 选择一个索引 $$$1 \leq i \leq n$$$,
- 设置 $$$a_i = a_i \cdot 2$$$。

如果 $$$b_i \leq b_{i+1}$$$ 对于所有 $$$1 \leq i < n$$$ 来说,数组 $$$b_1, b_2, \ldots, b_n$$$ 是非递减的。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。接下来是他们的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 数组 $$$a$$$ 的大小。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)。

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

输出

对于每个测试用例,输出使数组不减所需的最少操作数。

示例

输入 #1

9
1
1
2
2 1
3
3 2 1
4
7 1 5 3
5
11 2 15 7 10
6
1 8 2 16 8 16
2
624323799 708290323
12
2 1 1 3 3 11 12 22 45 777 777 1500
12
12 11 10 9 8 7 6 5 4 3 2 1

输出 #1

0
1
3
6
10
3
0
2
66

注意

第一个测试用例不需要任何操作。

在第二个测试用例中,我们需要选择 $$$i = 2$$$,之后数组将为 $$$[2, 2]$$$。

在第三个测试用例中,我们可以应用以下操作:

- 选择 $$$i = 3$$$,之后数组将为 $$$[3, 2, 2]$$$,
- 选择 $$$i = 3$$$,之后数组将为 $$$[3, 2, 4]$$$,
- 选择 $$$i = 2$$$,之后数组将为 $$$[3, 4, 4]$$$。