题目思路

原题的答案有问题，有一种简单的方法是求出每个数最少需要多少次变换从0得到，求出最大的数量，然后每次都[1, n]所有元素进行操作，执行最大数量就可以得到结果，那些所需操作更少的数只需要在一开始为0的时候不停的乘以2即可，这样就还是0.

但是原题可能认为第一个操作不能是乘以2，所以只能通过相邻两个数的操作次数的差值来求解，假设第i个数的操作次数是x，第i+1个数的操作次数为y，如果y大于x，那么i+1和i这两个数可以共用x次操作，还需要y-x次的操作。如果y小于x，那么y就可以共享所有x的操作，这里记差值为0。所以直接将相邻数的操作次数的差值累加即可。

关于每个数的操作次数：只需要将每个数的二进制的1的数量和其最大位的位置相加即可，1的数量对应于+1，最大位置意味着*2（左移一位）。

代码

题目描述

小红有一个长度为n且值都为0的数组a。对于这个致组小红每次操作可以选择一个区间[l, r]，对于[l,r]上的每一个数牛必须让其加一或者乘二(元素之间操作独立，可以选择些元素乘二，一些元素加一，但是区间内每个元素都要操作)

小红还有一个目标数组b，小红想知道对于初始数组a来说，其最少操作多少次可以将其变为b呢。

输入描述

第一行为，表示有t组数据

接下来有2t行，每组数据的第一行为一个n，第二行为n个整数，表示目标数组的元素b $1<=t<=10, 1<=n<=10^5, 1<=b_i<=10^9, \sum n<=10^5$

输出描述

输出为t行，每行为一组答案表示小红的最小操作次数

样例

输入

2
5
1 1 2 1 1
5
1 2 3 4 5

输出

2
4

说明 说明 第一组数据中，小红第一次选择区间[1,5]，让区间内所有元素加一，第二次小红选择区间[3,3]，让元素乘二。

第二组数据中，小红第一次选择区间(1,5]，让区间内所有元素加一。第二次小红选择区间[2,5]，让区间元素加一。第三次小红选择区间[3,5]，让a3加一，让a4,a5乘二。第四次小红选择区间[5,5]，让元素加一