AmShZ and G.O.A.T.
Contest: Codeforces Global Round 17
Difficulty rating: 2300
Tags: binary search, brute force, greedy, implementation, math

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.

Input format:
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$$$.

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
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

Example output:
0
1
2
3

Editorial:
We build the longest good subsequence starting with $$$a_s$$$ greedily step by step.
In each step we add the smallest possible element to the subsequence. If the last element is $$$a_k$$$, we have to find the minimum $$$i$$$ that $$$i > k$$$ and $$$a_i \ge 2 \cdot a_k - a_s$$$. (using lower_bound)
Assume $$$b_1 \neq b_2$$$, then $$$k < \log(a_n))$$$. Because for each $$$i$$$, $$$b_{i + 1} \ge 2 \cdot b_i - b_1$$$ then $$$b_{i + 1} - b_1 \ge 2 \cdot b_i - 2 \cdot b_1$$$ then $$$b_{i + 1} - b_1 \ge 2 \cdot (b_i - b_1)$$$.
And for cases that $$$b_1 = b_2$$$, $$$ + cnt_i$$$. ($$$cnt_i$$$ being the number of occurrences of element $$$i$$$)
So for each $$$i$$$ that $$$a_i \neq a_{i - 1}$$$ we do the above greedy approach. We don't need to do it for indices that $$$a_i = a_{i - 1}$$$ since adding $$$a_{i - 1}$$$ to the longest subsequence starting from $$$a_i$$$ doesn't make it bad.
Time complexity is $$$\log(n) \cdot \displaystyle\sum_{a_i \neq a_{i - 1}}{cnt_i + \log(a_n)} \le \log(n) \cdot \left( n \cdot \log(a_n) + \displaystyle\sum_{a_i \neq a_{i - 1}}{cnt_i} \right) \le \log(n) \cdot (n \cdot \log(a_n) + n)$$$.
The overall time complexity will be $$$\mathcal{O}(n \cdot \log n \cdot \log a_n)$$$