6574: Multiply 2 Divide 2
内存限制:512 MB
时间限制:7.500 S
评测方式:文本比较
命题人:
提交:4
解决:1
题目描述
Note:There is no dependency between this problem and problem Hack of Multiply 2 Divide 2.
Frank_DD has a sequence a of length n.
For each operation, he selects a number ai(1≤i≤n) and changes it to ai⋅2 or ⌊ai/2⌋.
Frank_DD wants to know the minimum number of operations to change the sequence a to a non-descending sequence.
Frank_DD has a sequence a of length n.
For each operation, he selects a number ai(1≤i≤n) and changes it to ai⋅2 or ⌊ai/2⌋.
Frank_DD wants to know the minimum number of operations to change the sequence a to a non-descending sequence.
输入
The first line of the input contains one integer T (1≤T≤5 ) --- the number of test cases. Then T test cases follow.
In each test case:
The first line contains a single integer n(1≤n≤10^5) --- the length of sequence a.
The second line contains n integers a1,a2,…,an (1≤ai≤10^5) --- the sequence a.
In each test case:
The first line contains a single integer n(1≤n≤10^5) --- the length of sequence a.
The second line contains n integers a1,a2,…,an (1≤ai≤10^5) --- the sequence a.
输出
For each test case, print a single integer in a single line --- the minimum number of operations to change the sequence aa to a non-descending sequence.
样例输入 复制
2
7
6 3 3 4 10 8 2
10
9 9 4 7 3 10 10 8 4 3
样例输出 复制
4
11
提示
In the first test case, we can use at least 4 operations to change the sequence a to a non-descending sequence:
a1=⌊a1/2⌋
a5=⌊a5/2⌋
a7=a7⋅2
a7=a7⋅2
a1=⌊a1/2⌋
a5=⌊a5/2⌋
a7=a7⋅2
a7=a7⋅2