题目描述

在一个遥远的王国里，有一位年轻的魔法师，她在一座古老的塔楼中学习魔法。她偶然发现了一本神秘的书籍，书里写着关于如何将一组数字变得“非递减”——也就是每个数字都小于或等于后一个数字。这个过程是通过一种叫做“加倍”的魔法实现的，每次她只能选择一个数字，然后将它加倍。

魔法师很快意识到，如果她能成功地施展这个魔法，她将获得一个巨大的奖励，甚至能够掌握改变整个王国命运的力量。因此，她决定挑战这个任务——将一组数字变为非递减数组，并且尽量减少她所施展的加倍次数。

她从一本古老的卷轴上找到了一个算法，告诉她在面对每组数字时如何最有效地执行加倍操作。

任务： 给定一个整数数组 ($a_1$, $a_2$, $\dots$, $a_n$)，魔法师需要通过最少的加倍操作使得这个数组变成非递减的。在每一次操作中，她可以选择数组中的一个元素，将它乘以 2。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $t$ ( $1 \leq t \leq 10^4$ ) - 测试用例的数量。随后是测试用例说明。

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

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

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

输出

对于每个测试用例，输出将数组变为非递减数组所需的最小操作次数。

测试样例：

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

输出样例：

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])。

来源

题目.md code.cpp 题解