題目鏈接：1610E - AmShZ and G.O.A.T.

既然要求的是最大的好序列，就需要考慮排除所有的不安定因素，即先思考什么樣的子序列是非法的。

\(k=1,2\) 的時候可以發現都是合法情況，那么看一下 \(k=3\) 的情況，可以得出非法的情況只可能是 \(c_1<\frac{c_1+c_2+c_3}{3}<c_2\le c_3\)，分析一下可以得出，對應的充要條件實際上是 \(\frac{c_1+c_2+c_3}{3}<c_2\)，可以化成 \(c_1+c_3<2c_2\)。

另外可以證明，一個非法序列 \(c\) 里一定存在一個長度為 \(3\) 的非法子序列，證明方式采用反證法。

令 \(m=\lceil \frac{k}{2}\rceil\)，考慮 \(c_m\) 的大小，既然 \(c\) 是一個非法序列，那么 \(c_m\) 就一定要嚴格大于序列的平均值。然而由于 \(c\) 中不存在一個長度為 \(3\) 的非法子序列，據此得出對任意的 \(i\)，\(c_i,c_m,c_{k-i+1}\) 一定是一個合法序列，那么就有 \(c_i+c_{k-i+1}\ge 2c_m\)（這一結論在 \(i=m\) 或 \(k-i+1=m\) 時也顯然成立）。把 \(\sum c_i\) 乘以二后首尾配對就能得到：

把上面的這個式子兩邊同除 \(2k\) 就能得出，\(c_m\le \frac{\sum_{i=1}^k c_i}{k}\) ，與之前的 \(c_m\) 要嚴格大于序列的平均值發生矛盾，于是得出 \(c\) 里一定存在一個長度為 \(3\) 的非法子序列，證畢。

于是一個好的序列就必須保證：序列中不存在三個數 \(a\le b\le c\)，使得 \(2b>a+c\)。必要性顯然，充分性在剛剛得到了證明。

那么我們在構造一個盡可能大的子序列時，就需要時刻保證對任意的 \(a\le b\le c\)，有 \(b\le \frac{a+c}{2}\)。我們來考慮一下往答案序列里面一直加數的過程，假設一開始序列里有兩個數 \(x,y\)，不妨設 \(x,y\) 就分別是最終答案中的最小值和最大值，那么下一個被加進來的數就必須滿足 \(x\le z\le \frac{x+y}{2}\)。不難通過想象（或在數軸上畫圖）得出，這一操作相當于讓前兩個數之間的間隔減半。于是這個加數的操作不會超過 \(O(\log n)\) 次，當然除了最后可能會把所有與 \(x\) 相同的數字全部加進去。

回顧這個構造序列的過程，本著貪心的原則可以得出，當確定了序列中的最小值 \(a\) 之后，一定是先把所有數字中的最大值加進去來提高初始兩個數之間的間隔。接下來就是不斷加入最大的滿足 \(x\le z\le \frac{x+y}{2}\) 的數字 \(z\)，這樣就能構造出一個以 \(a\) 為最小值的最大序列。這里要注意，由于在序列中，只有最小值是可以重復出現的（若不然，則會有 \(\{x,y,y\},x<y\) 使得序列變壞），所以序列的最小值是需要枚舉的。那么我們枚舉序列中的最小值，然后再模擬生成序列的過程，每次二分找到最大的滿足條件的數，就能得到最終的答案，時間復雜度為 \(O(n\log n\log W)\)。

當然作為一篇嚴謹的題解，我們還需要補充說明一下，按照此法生成的序列一定是一個好序列。實際上只要說明任意一個大小為 \(3\) 的子序列都是合法序列就好了，以下為證明過程：

對這個生成的序列 \(b\)，可以根據生成序列的過程得出，\(b_{i}\le \frac{b_{i+1}+b_1}{2}\)，從而有 \(b_{i+1}-b_1\ge 2(b_i-b_1)\)。那么對任意的 \(j>i\)，也能得出 \(b_j-b_1\ge 2(b_i-b_1)\)，移項得到 \(b_j-b_i\ge b_i-b_1\)。

于是對任意的 \(i<j<k\)，必然有 \(b_k-b_j\ge b_j-b_1\ge b_j-b_i\)，從而推出 \(2b_j\le b_i+b_k\)，得到 \(b_i,b_j,b_k\) 是一個合法序列，證畢。

#include<bits/stdc++.h>
using namespace std;
#define N 200010
int T,n,a[N];
int main()
{
	scanf("%d",&T);
	while(T--){
		int ans=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		for(int i=1,nxt=1;i<=n;i=nxt){
			while(nxt<=n && a[nxt]==a[i])nxt++;
			if(nxt>n){
				ans=max(ans,nxt-i);
				break;
			}
			int j=n,cnt=1;
			while(nxt<=j){
				j=upper_bound(a+nxt,a+j,(a[i]+a[j])/2)-a-1;
				if(j<nxt)break;
				cnt++;
			}
			ans=max(ans,cnt+nxt-i);
		}
		printf("%d\n",n-ans);
	}
}