AmShZ and G.O.A.T. solution codeforces

AmShZ and G.O.A.T. solution codeforces

Let’s call an array of 𝑘k integers 𝑐1,𝑐2,,𝑐𝑘c1,c2,…,ck terrible, if the following condition holds:

  • Let 𝐴𝑉𝐺AVG be the 𝑐1+𝑐2++𝑐𝑘𝑘c1+c2+…+ckk(the average of all the elements of the array, it doesn’t have to be integer). Then the number of elements of the array which are bigger than 𝐴𝑉𝐺AVG should be strictly larger than the number of elements of the array which are smaller than 𝐴𝑉𝐺AVG. Note that elements equal to 𝐴𝑉𝐺AVG don’t count.

    For example 𝑐={1,4,4,5,6}c={1,4,4,5,6} is terrible because 𝐴𝑉𝐺=4.0AVG=4.0 and 55-th and 44-th elements are greater than 𝐴𝑉𝐺AVG and 11-st element is smaller than 𝐴𝑉𝐺AVG.

Let’s call an array of 𝑚m integers 𝑏1,𝑏2,,𝑏𝑚b1,b2,…,bm bad, if at least one of its non-empty subsequences is terrible, and good otherwise.

You are given an array of 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an. Find the minimum number of elements that you have to delete from it to obtain a good array.

An array is a subsequence of another array if it can be obtained from it by deletion of several (possibly, zero or all) elements.

AmShZ and G.O.A.T. solution codeforces Input

The first line contains an integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer 𝑛n (2𝑛21052≤n≤2⋅105) — the size of 𝑎a.

The second line of each testcase contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖1091≤ai≤109) — elements of array 𝑎a.

In each testcase for any 1𝑖<𝑛1≤i<n it is guaranteed that 𝑎𝑖𝑎𝑖+1ai≤ai+1.

It is guaranteed that the sum of 𝑛n over all testcases doesn’t exceed 21052⋅105.

Output

For each testcase, print the minimum number of elements that you have to delete from it to obtain a good array.

Example
input

AmShZ and G.O.A.T. solution codeforces Copy

4
3
1 2 3
5
1 4 4 5 6
6
7 8 197860736 212611869 360417095 837913434
8
6 10 56026534 405137099 550504063 784959015 802926648 967281024
output

Copy
0
1
2
3
Note

In the first sample, the array 𝑎a is already good.

In the second sample, it’s enough to delete 11, obtaining array [4,4,5,6][4,4,5,6], which is good.

 

Leave a Comment

Your email address will not be published. Required fields are marked *