问题 6643 --龙哥的不下降数列

6643: 龙哥的不下降数列★★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 31  解决: 3
[提交][状态][命题人:]

题目描述

给定长度为n的序列 a，你可以进行以下操作。
  • 选取一个i满足1≤i≤n，使ai变为原来的2倍。
现在请你帮忙计算一下最少需要几次操作使得a成为一个不下降的序列。

输入

第一整数为T,表示有T (1≤T≤10000)组测试样例。
每组测试样例的第一行为n (1≤n≤1e5),表示序列的长度。
第一行为n个整数a1,a2,…,an (1≤ai≤1e9)。
测试数据确保所有的n之和不超过2e5。

输出

每组测试样例输出一个整数k，表示使a成为不下降的序列的最少操作次数。

样例输入
Copy
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
样例输出
Copy
0
1
3
6
10
3
0
2
66

提示

在第1组测试数据中，不需要操作。
在第2组测试数据中，选择第2个数字操作1次后，得到[2,2]。
在第3组测试数据中，进行如下操作：
  选择第3个数字操作1次后，得到[3,2,2]；
  选择第3个数字再操作1次后，得到[3,2,4]；
  选择第2个数字操作1次后，得到 [3,4,4]。

来源

 

[提交][状态]