rt，TLE on #14，大概是时限的 1.5 倍左右。算法为 set 维护非递增位置，二分线段树求前缀后缀。时间复杂度 $\Theta(n\log(n+q))$。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
const int inf=1e9;
int n,a[N];
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
	return x*f;
}
void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9){
		write(x/10);
	}
	putchar(x%10+'0');
}
struct DP{
	int maxn=-inf,minn=inf;
	inline void cpy(int val){
		maxn=minn=val;
	}
	inline friend DP operator+(DP A,DP B){
		DP C;
		C.maxn=max(A.maxn,B.maxn);
		C.minn=min(A.minn,B.minn);
		return C;
	}
};
struct node{
	int ch[2];
	DP val;
}tr[N<<1];
int rt,idx;
struct segTree{
	#define lc tr[i].ch[0]
	#define rc tr[i].ch[1]
	#define mid (l+r)/2
	void pushup(int i){
		tr[i].val=tr[lc].val+tr[rc].val;
	}
	void build(int &i,int l,int r){
		i=++idx;
		if(l==r){
			tr[i].val.cpy(a[l]);
			return;
		}
		build(lc,l,mid);
		build(rc,mid+1,r);
		pushup(i);
	}
	void modify(int i,int l,int r,int x){
		if(l==r){
			tr[i].val.cpy(a[x]);
			return;
		}
		if(x<=mid){
			modify(lc,l,mid,x);
		}else{
			modify(rc,mid+1,r,x);
		}
		pushup(i);
	} 
	DP query(int i,int l,int r,int L,int R){
		if(L<=l&&R>=r){
			return tr[i].val;
		}
		if(R<=mid){
			return query(lc,l,mid,L,R);
		}else if(L>mid){
			return query(rc,mid+1,r,L,R);
		}else{
			return query(lc,l,mid,L,R)+query(rc,mid+1,r,L,R);
		}
	}
	#undef lc
	#undef rc
	#undef mid
}sgt;
set<int>s;
inline void add(int x){
	if(x-1>0&&a[x]<a[x-1]){
//		printf("Add:%d\n",x);
		s.insert(x);
	}
	if(x+1<=n&&a[x]>a[x+1]){
//		printf("Add:%d\n",x+1);
		s.insert(x+1);
	}
}
inline void del(int x){
	if(x-1>0&&a[x]<a[x-1]){
//		printf("Del:%d\n",x);
		s.erase(x);
	}
	if(x+1<=n&&a[x]>a[x+1]){
//		printf("Del:%d\n",x+1);
		s.erase(x+1);
	}
}
inline int lFind(int l,int r){
//	printf("%d %d\n",l,r);
	int res=0;
	while(l<=r){
		int mid=(l+r)/2;
		if(mid==n){
			res=mid;
			l=mid+1;
		}else{
			DP val1=sgt.query(rt,1,n,1,mid),val2=sgt.query(rt,1,n,mid+1,n);
			if(val1.maxn<=val2.minn){
				res=mid;
				l=mid+1;
			}else{
				r=mid-1;
			}
		}
	}
	return res;
}
inline int rFind(int l,int r){
//	printf("%d %d\n",l,r);
	int res=n+1;
	while(l<=r){
		int mid=(l+r)/2;
		if(mid==1){
			res=mid;
			r=mid-1;
		}else{
			DP val1=sgt.query(rt,1,n,1,mid-1),val2=sgt.query(rt,1,n,mid,n);
			if(val1.maxn<=val2.minn){
				res=mid;
				r=mid-1;
			}else{
				l=mid+1;
			}
		}
	}
	return res;
}
inline void print(){
	if(s.empty()){
		write(-1);
		putchar(' ');
		write(-1);
		putchar('\n');
	}else{
		write(lFind(1,*s.begin()-1)+1);
		putchar(' ');
		write(rFind(*--s.end(),n)-1);
		putchar('\n');
	}
} 
inline void solve(){
	s.clear();
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	for(int i=1;i<=n;i=i+2){
		add(i);
	}
	sgt.build(rt,1,n);
	print();
	int q=read();
	for(register int i=1;i<=q;++i){
		int pos=read(),val=read();
		del(pos);
		a[pos]=val;
		sgt.modify(rt,1,n,pos);
		add(pos);
//		printf("%d %d\n",*s.begin(),*--s.end());
		print();
	}
}
int main(){
	int T=read();
	while(T--){
		solve();
	}
	return 0;
}