AT_arc197_b [ARC197B] Greater Than Average

Define the **score** of a non-empty integer sequence $ x = (x_1, \ldots, x_n) $ as the number of elements of $ x $ that are strictly greater than the average of $ x $ . That is, the score of $ x $ is the count of indices $ i $ satisfying $ x_i > \dfrac{x_1+\cdots+x_n}{n} $ . You are given a length- $ N $ integer sequence $ A = (A_1, \ldots, A_N) $ . Find the maximum score of a non-empty subsequence of $ A $ . There are $ T $ test cases; solve each one. Definition of subsequenceA subsequence of $ A $ is any sequence obtained by deleting zero or more elements from $ A $ and keeping the remaining elements in their original order.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \vdots $ $ \text{case}_T $ Each case is given in the following format: > $ N $ $ A_1 $ $ \cdots $ $ A_N $

Print $ T $ lines. The $ i $ -th line should contain the maximum score of a non-empty subsequence of $ A $ for the $ i $ -th test case.

### Sample Explanation 1 For the first test case, below are examples of subsequences, their averages, and their scores. - $ x = (A_1) = (2) $ : the average is $ 2 $ , and the score is $ 0 $ . - $ x = (A_3,A_5) = (5,5) $ : the average is $ 5 $ , and the score is $ 0 $ . - $ x = (A_1,A_3,A_4,A_5) = (2,5,7,5) $ : the average is $ \frac{19}{4} $ , and the score is $ 3 $ . - $ x = (A_1,A_2,A_3,A_4,A_5) = (2,6,5,7,5) $ : the average is $ 5 $ , and the score is $ 2 $ . ### Constraints - $ 1\le T\le 2\times 10^5 $ - $ 2\le N\le 2\times 10^5 $ - $ 1\le A_i\le 10^9 $ - All input values are integers. - The sum of $ N $ over all test cases is at most $ 2\times 10^5 $ .