题目描述

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

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

注意：你不能在第一次进行乘2操作。

输入描述

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

接下来有2×t行，每组数据的第一行为一个n。

第二行为n个整数，表示目标数组的元素bi。

1 <= t <= 10;

1 <= n <= 1e5;

1 <= bi <= 1e9;

Σn <= 1e5.

输出描述

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

输入示例

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

输出示例

2
4

提示信息

第一组数据，选择[0, 4]加一；然后选[2, 2]择加一；

第二组数据，选择[0, 4]加一；然后[1, 4]加一；再对区间[2, 4]中 -> [3, 4]乘2, [2, 2]加一；最后[4, 4]加一。

时间限制：c/c++：1s；go：2s；java：5s；其他语言：6s。