CF1610E.AmShZ and G.O.A.T.

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.

我们称一个包含 $k$ 个整数的数组 $c_1, c_2, \ldots, c_k$ 是糟糕的（terrible），如果满足以下条件：

• 设 $AVG = \frac{c_1 + c_2 + \ldots + c_k}{k}$（即该数组所有元素的平均值，不一定是整数）。那么，数组中严格大于 $AVG$ 的元素个数必须严格大于数组中严格小于 $AVG$ 的元素个数。注意：等于 $AVG$ 的元素不计入比较。

  例如，数组 $c = \{1, 4, 4, 5, 6\}$ 是糟糕的，因为 $AVG = 4.0$，其中第 $4$ 和第 $5$ 个元素（即 $5$ 和 $6$）大于 $AVG$，而第 $1$ 个元素（即 $1$）小于 $AVG$。

我们称一个包含 $m$ 个整数的数组 $b_1, b_2, \ldots, b_m$ 是坏的（bad），如果它至少存在一个非空子序列是糟糕的；否则称其为好的（good）。

现给你一个包含 $n$ 个整数的数组 $a_1, a_2, \ldots, a_n$。求最少需要从中删除多少个元素，才能使其变为一个好的数组。

若一个数组可通过从另一数组中删除若干（可能为零或全部）元素得到，则称其为该数组的一个子序列。

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$.

第一行包含一个整数 $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$。

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

对于每个测试用例，输出为使数组变为“好数组”所需删除的最少元素个数。

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.

在第一个样例中，数组 $a$ 已经是“好”的。

在第二个样例中，只需删除 $1$，得到数组 $[4, 4, 5, 6]$，该数组是“好”的。