如果满足以下条件,我们称 $$$k$$$ 整数数组 $$$c_1, c_2, \ldots, c_k$$$ 为可怕的:
- 让 $$$AVG$$$ 为 $$$\frac{c_1 + c_2 + \ldots + c_k}{k}$$$(数组所有元素的平均值,不一定是整数)。那么数组中大于 $$$AVG$$$ 的元素数量应严格大于数组中小于 $$$AVG$$$ 的元素数量。请注意,等于 $$$AVG$$$ 的元素不算数。例如 $$$c = \{1, 4, 4, 5, 6\}$$$ 很糟糕,因为 $$$AVG = 4.0$$$ 和 $$$5$$$-th 和 $$$4$$$-th 元素大于 $$$AVG$$$ 且 $$$1$$$-st 元素小于 $$$AVG$$$。
如果 $$$m$$$ 整数数组 $$$b_1, b_2, \ldots, b_m$$$ 是坏的,如果它的至少一个非空子序列是糟糕的,否则是好的。
给你一个 $$$n$$$ 整数数组 $$$a_1, a_2, \ldots, a_n$$$。求出为了获得一个好的数组而必须从中删除的最小元素数。
如果一个数组可以通过删除几个(可能是零个或全部)元素来获得,那么它就是另一个数组的子序列。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — $$$a$$$ 的大小。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。
在任何 $$$1 \le i \lt n$$$ 的每个测试用例中,保证 $$$a_i \le a_{i+1}$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印必须从中删除以获得良好数组的最小元素数。
示例
输入 #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
注意
在第一个示例中,数组 $$$a$$$ 已经很好了。
在第二个示例中,删除 $$$1$$$ 就足够了,获得数组 $$$[4, 4, 5, 6]$$$,这很好。