AmShZ and G.O.A.T.

题意翻译

定义一个长度为 $k$ 的序列 $c$ 是「毒瘤的」，当且仅当： - 令 $AVG$ 为 $\frac{\sum_{i=1}^kc_i}{k}$，即整个序列的平均值（注意它并不一定是整数）。若序列中大于 $AVG$ 的元素数量严格大于小于 $AVG$ 的元素数量，那么该序列为毒瘤的（注意到，等于 $AVG$ 的数并没有被计算在内）。 例如 $c={1,4,4,5,6}$ 是毒瘤的，因为 $AVG=4.0$，而 $c_4,c_5$ 大于 $AVG$，仅有 $c_1$ 小于 $AVG$。 而我们称序列 $b$ 是坏的，当且仅当其存在一个非空子序列为毒瘤的。若序列 $b$ 不是坏的，那么它是好的。 蓝给出了一个长度为 $n$ 的序列 $a$，她希望你能算出至少要从中删除多少数，才能使其成为一个好的序列。 本题含多组数据。第一行含一个整数 $t$ 代表数据组数，之后每行你需要依次读入 $n$ 与序列 $a$。 本题数据保证：$1 \leq t \leq 10^4，2 \leq n \leq 2\times10^5，2 \leq \sum n \leq 2\times10^5，1 \leq a_i \leq 10^9$。 特别的，对于所有 $i\in[1,n-1]$，有 $a_i\le a_{i+1}$。

题目描述

Let's call an array of $ k $ integers $ c_1, c_2, \ldots, c_k $ terrible, if the following condition holds: - Let $ AVG $ be the $ \frac{c_1 + c_2 + \ldots + c_k}{k} $ (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 $ c = \{1, 4, 4, 5, 6\} $ is terrible because $ AVG = 4.0 $ and $ 5 $ -th and $ 4 $ -th elements are greater than $ AVG $ and $ 1 $ -st element is smaller than $ AVG $ . Let's call an array of $ m $ integers $ b_1, b_2, \ldots, b_m $ bad, if at least one of its non-empty subsequences is terrible, and good otherwise. You are given an array of $ n $ integers $ a_1, a_2, \ldots, a_n $ . 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.

输入输出格式

输入格式

The first line contains an integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ) — the size of $ a $ . The second line of each testcase contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — elements of array $ a $ . In each testcase for any $ 1 \le i \lt n $ it is guaranteed that $ a_i \le a_{i+1} $ . It is guaranteed that the sum of $ n $ over all testcases doesn't exceed $ 2 \cdot 10^5 $ .

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

0
1
2
3

说明

In the first sample, the array $ a $ is already good. In the second sample, it's enough to delete $ 1 $ , obtaining array $ [4, 4, 5, 6] $ , which is good.