回看

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

给定一个长度为 $n$ 的整数数组 $a_1,a_2,\ldots,a_n$。每次操作可以选择一个下标 $1\le i\le n$，将 $a_i$ 替换为 $2a_i$。

求使数组变为非递减数组所需的最少操作次数。数组非递减指对所有 $1\le i<n$，均有 $a_i\le a_{i+1}$；相邻元素可以相等。

输入格式

第一行包含一个整数 $t$，表示测试数据的组数。

每组测试数据第一行包含一个整数 $n$。第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对于每组测试数据，输出使数组变为非递减所需的最少操作次数。

样例输入 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

样例解释

第一组不需要操作。

第二组将第二个数乘以 $2$，数组变为 $[2,2]$。

第三组可以先将第三个数乘以 $2$ 两次，再将第二个数乘以 $2$ 一次，得到 $[3,4,4]$，共需 $3$ 次操作。

数据范围

对于所有测试数据，$1\le t\le10000$，$1\le n\le100000$，$1\le a_i\le1000000000$。同一个输入文件内，所有测试数据的 $n$ 之和不超过 $200000$。