考虑最简单的情况,如果三个数abc(a<b<c){a、b、c(a<b<c)},有ba<=cb{b-a<=c-b},那么这三个数是非terrible{terrible}的;反之是terrible{terrible}的。那么一个数组中如果存在相邻三个数的差分递减,那么这个数组不是good{good}的。

考虑任意三个数的差分不递减,如图所示: alt

我们只需要满足bkbk1>=bk1b1{b_k-b_{k-1}>=b_{k-1}-b_1},(b1{b_1}是数组中最小的值),那么得到任意三个数的差分一定不递减,否则一定有存在三个数的差分递减。

相邻两个数的差分不递减的数组一定是非terrible{terrible}的,所以满足任意三个数的差分不递减的数组就是good{good}的。

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=2e5+7,mod=1e9+7;
void solve() {
	int n,ans(2),res(0);
	cin>>n;
	vector<int>a(n);
	for(auto &i:a) cin>>i;
	for(int i=0,j;i<n-1;++i) {
		j=i+1;
		while(j<n&&a[j]==a[i]) ++j;
		res=j-i;
		j-=1,i=j;
		while(1) {
			auto it=lower_bound(a.begin()+j+1,a.end(),a[j]+(a[j]-a[i]));
			if(it==a.end()) break;
			++res;
			j=it-a.begin();
		}
		ans=max(ans,res);
	}
	cout<<n-ans<<'\n';
}
int main() {
	cin.sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	int _=1;
	cin>>_;
	while(_--) solve();
	return 0;
}