C. Water the Trees Educational Codeforces Round 126 (Rated for Div. 2)

There are nn trees in a park, numbered from 11 to nn. The initial height of the ii-th tree is hihi.

You want to water these trees, so they all grow to the same height.

The watering process goes as follows. You start watering trees at day 11. During the jj-th day you can:

• Choose a tree and water it. If the day is odd (e.g. 1,3,5,7,…1,3,5,7,…), then the height of the tree increases by 11. If the day is even (e.g. 2,4,6,8,…2,4,6,8,…), then the height of the tree increases by 22.
• Or skip a day without watering any tree.

Note that you can't water more than one tree in a day.

Your task is to determine the minimum number of days required to water the trees so they grow to the same height.

You have to answer tt independent test cases.

Input

The first line of the input contains one integer tt (1≤t≤2⋅1041≤t≤2⋅104) — the number of test cases.

The first line of the test case contains one integer nn (1≤n≤3⋅1051≤n≤3⋅105) — the number of trees.

The second line of the test case contains nn integers h1,h2,…,hnh1,h2,…,hn (1≤hi≤1091≤hi≤109), where hihi is the height of the ii-th tree.

It is guaranteed that the sum of nn over all test cases does not exceed 3⋅1053⋅105 (∑n≤3⋅105∑n≤3⋅105).

Output

For each test case, print one integer — the minimum number of days required to water the trees, so they grow to the same height.

Example

input

Copy

3
3
1 2 4
5
4 4 3 5 5
7
2 5 4 8 3 7 4

output

Copy

4
3
16

思路：因为我们是奇数天+1，偶数天+2，所以奇数天必须大于等于偶数天，不是随便的天数，那么根据贪心我们应该把所有的天数都变成最大值，然而遇到1 1 1 1 1 1 2这种情况我们最少的天数是把2先变成3然后再把所有都变成3，所以我们判断天数能不能把所有数组都变成最大数或者都变成最大数+1，如果能天数就符合。

最大最小值用2分来解决，列举天数x，奇数天表示为x-x/2，偶数天表示为x/2，然后我们再看看这些天能不能将所有数组都变成最大值或者最大值加一就行了。

核心是cheek函数：把奇数天数的个数one，偶数的天数和最大值传入数组，我们遍历数组，如果a[i]<max，那么我们算出他的差值x，先用偶数天数two来填x，如果偶数天数不够的话，把偶数天数用完再用奇数天数，最后看看奇数天数是否大于等于0就行了。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
const int N=300005;
typedef long long ll;
ll a[N];
ll b[N];
bool cheek(ll one,ll two,ll max1){
	for(int i=1;i<=n;i++){
		if(a[i]<max1){
			ll x=max1-a[i];
			if(x/2<=two){
				two-=x/2;
				one-=x%2;
			}else{
				x-=two*2;
				two=0;
				one-=x;
			}
		}
	}
	if(one<0){
		return false;
	}else return true;
}
void sove(){
	cin>>n;
	ll max1=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		max1=max(max1,a[i]);
	}
	ll l=0,r=1e18;
	while(l<r){
		ll mid=l+r>>1;
		if(cheek(mid-mid/2,mid/2,max1)||cheek(mid-mid/2,mid/2,max1+1)){
			r=mid;
		}else l=mid+1;
	}
	cout<<l<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie() ,cout.tie() ;
	int t=1;
	cin>>t;
	while(t--){
		sove();
	}
	return 0;
}