评测记录

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pll;
typedef deque<pll>dp;
const ll N=1e6+10;
ll T,n,k,x,y,a[N],dt[N],ln,ans,flag;
dp p,q;
inline void uin(ll&ret){
    ll x=0,f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
		f|=ch=='-',ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch-48),ch=getchar();
    ret=(f?-x:x);
}
inline void uout(ll ps){
	if(ps<0) putchar('-'),ps=-ps;
	if(ps==0){
		putchar('0');
		return ;
	}
	if(ps>=10ll) uout(ps/10ll);
	putchar(ps%10ll+'0');
}
void init(){
	p.clear(),q.clear();
	for(ll i=1;i<=n;i++) p.push_back({a[i],i});
}
pll demax(){
	pll res;
	if(q.empty()) 				res=p.back(),p.pop_back(),flag|=2;
	else if(p.empty()) 			res=q.back(),q.pop_back();
	else if(p.back()>q.back()) 	res=p.back(),p.pop_back(),flag|=2;
	else 						res=q.back(),q.pop_back();
	return res;
}
pll demin(){
	pll res;
	if(q.empty()) 				res=p.front(),p.pop_front(),flag=1;
	else if(p.empty()) 			res=q.front(),q.pop_front(),flag=0;
	else if(p.front()<q.front())res=p.front(),p.pop_front(),flag=1;
	else 						res=q.front(),q.pop_front(),flag=0;
	return res;
}
pll gtmin(){
	if(q.empty()) 				return p.front();
	else if(p.empty()) 			return q.front();
	else if(p.front()<q.front())return p.front();
	else 						return q.front();
}
inline void dfs(ll dep){
	if(dep==n-1){
		ln=dep;dt[gtmin().second]=0x3f3f3f3f;
		return ;
	}
	pll fmin=demin(),smin=gtmin(),fmax=demax();
	if(fmax.first-fmin.first>smin.first){
		q.push_front({fmax.first-fmin.first,fmax.second});
		dt[fmin.second]=dep;
		dfs(dep+1);
		q.pop_front();
	}
	else{
		q.push_front({fmax.first-fmin.first,fmax.second});
		dt[fmin.second]=dep;
		dfs(dep+1);
		q.pop_front();
		if(dt[fmax.second]<ln){
			ln=dep;
			dt[fmin.second]=0x3f3f3f3f;
			ans=n-dep;
		}
	}
	if(flag&1)	p.push_front(fmin);
	else 		q.push_front(fmin);
	if(flag&2)	p.push_back(fmax);
	else		q.push_back(fmax);
}
int main(){
	uin(T);
	for(ll I=0;I<T;I++){
		if(!I){
			uin(n);
			for(ll i=1;i<=n;i++) uin(a[i]);
		}
		else{
			cin>>k;
			while(k--){uin(x),uin(y),a[x]=y;}
		}
		init();
		memset(dt,63,sizeof(dt));
		ans=1;
		ln=-114514;
		dfs(0);
		uout(ans);puts("");
	}
	return 0;
}