Life Is All About Balance

sayeef006 Criterion 2022 Round 17
Limits 1s, 512 MB

Given an array AA of NN integers, the array will be balanced if you can select at least one index i(1i<N)i(1 \leq i < N) and divide the array into two non empty subarrays, BB == {A1,A2,..,Ai}\{A_1, A_2, .. , A_i\} and CC == {Ai+1,Ai+2,..,AN}\{A_{i+1}, A_{i+2}, .. , A_N\} such that F(B)=F(C)F(B) = F(C).

F(V)F(V) for the subarray VV is defined as the difference between the maximum and the minimum element of VV. For example if VV ={3,6,2,0}{= \{3, 6, 2, 0\}}, then F(V)F(V) =max{3,6,2,0}min{3,6,2,0}{= max \{3, 6, 2, 0\} - min \{3, 6, 2, 0\}} =60{= 6 - 0} =6{= 6}.

Before dividing the array, you can do one type of operation to the array any number of times(possibly zero). Select any index j(1jN)j(1 \leq j \leq N) and any integer x(0x2×109)x(0 \leq x \leq 2 \times 10^9) and set AjA_j = xx.

You need to output the minimum number of operations required to make the array balanced. It is guaranteed that any array can be made balanced under the given constraints by applying a finite number of operations.

Input

The input contains multiple test cases. The first line of input contains one integer TT(1T2×104)(1 \leq T \leq 2\times10^4)- the number of test cases.

The first line of each test case contains one integer NN(2N5×105)(2 \leq N \leq 5\times10^5)- the size of the array.

The second line of each test case contains NN integers A1,A2,..,ANA_1, A_2,.. , A_N (0Ai109)(0 \leq A_i \leq 10^9).

It is guaranteed that the sum of NN over all test cases does not exceed 5×1055\times10^5.

Output

For each test case, print one integer - the minimum number of operations required to make the array balanced.

Sample

InputOutput
2
2
12 12
6
1 3 6 10 6 4
0
1

For the first test case, the array is already Balanced.

For the second test case, we can do one operation to make the array Balanced. We can select jj =4= 4 and xx =9= 9 and set A4A_4 =9= 9. Then the array will be {1,3,6,9,6,4}{\{1, 3, 6, 9, 6, 4\}}. We can select index ii =3= 3 to divide the array into two subarrays, B={1,3,6}B = \{1, 3, 6\} and C={9,6,4}C = \{9, 6, 4\}. F(B)F(B) =max{1,3,6}{= max\{1, 3, 6\}} - min{1,3,6}{min\{1, 3, 6\}} =61= 6 - 1 =5= 5. F(C)F(C) =max{9,6,4}= max\{9, 6, 4\} - min{9,6,4}min\{9, 6, 4\} =94= 9 - 4 =5= 5. So the array is Balanced.


Submit

Login to submit.

Statistics

69% Solution Ratio
serotoninEarliest, 1M ago
Sumaya_1703110Fastest, 0.0s
serotoninLightest, 4.2 MB
serotoninShortest, 632B
Toph uses cookies. By continuing you agree to our Cookie Policy.