CF1905F

*2600？*2100！

考虑一个位置 $i$，考虑什么时候交换 $x,y(x<y)$ 位置的数，它会对答案有 $1$ 的贡献。

• $\sum_{j<i}[p_j>p_i]>1$ 或 $\sum_{j>i}[p_j<p_i]>1$。

显然这种情况下是不可能使 $i$ 有贡献的。

• $\exist j<i,p_j>p_i$ 且 $\exist j>i,p_j<p_i$。

此时当且仅当交换这两个 $j$ 的位置时，会使 $i$ 有贡献。

• 否则。

无法通过交换两个不为 $i$ 的位置使 $i$ 产生贡献。

还有一种情况：交换了 $i$ 和另一个位置，使得 $i$ 有贡献。

记录 $pl_i$ 表示最大的 $j$ 使得 $p_j<p_i$，$pr_i$ 表示最小的 $j$ 使得 $p_j>p_i$。则当 $pl_i<pr_i$ 时：

• $i<pl_i$。

交换 $i$ 和 $pl_i$ 使其有贡献。

• $i>pr_i$。

交换 $i$ 和 $pr_i$ 使其有贡献。

以上就是所有可能新增贡献的情况。但是原本有贡献的位置会不会变没有呢？

显然不会，因为我们不会交换 $x,y(p_x<p_y)$。

除非？

除非整个序列升序。特判即可。

至于维护上面的东西，第一部分用一个 set 再扫描线一下。第二部分是一个值域上的前缀 $\max$ 后缀 $\min$。再用一个 map 记录所有有贡献的 $x,y$，如果没有一个 $x,y$ 则说明原序列升序，特判。

code：

int n,m,a[N],b[N],f[N],g[N],pf[N],pg[N];
map<pii,int> c;
set<pii> st;
void Yorushika(){
	scanf("%d",&n);
	rep(i,1,n)scanf("%d",&a[i]),b[a[i]]=i;
	st.clear();
	rep(i,1,n){
		if(st.size()>1&&prev(prev(st.end()))->fi>a[i])f[i]=-1;
		else if(st.size()&&prev(st.end())->fi>a[i])f[i]=prev(st.end())->se;
		else f[i]=0;
		st.emplace(a[i],i);
	}
	st.clear();
	drep(i,n,1){
		if(st.size()>1&&next(st.begin())->fi<a[i])g[i]=-1;
		else if(st.size()&&st.begin()->fi<a[i])g[i]=st.begin()->se;
		else g[i]=0;
		st.emplace(a[i],i);
	}
	int sum=0;c.clear();
	rep(i,1,n){
		if(f[i]>0&&g[i]>0)c[Mp(f[i],g[i])]++;
		if(!f[i]&&!g[i])sum++;
	}
	pf[1]=b[1],pf[0]=0;
	rep(i,2,n)pf[i]=max(b[i],pf[i-1]);
	pg[n]=b[n],pg[n+1]=n+1;
	drep(i,n-1,1)pg[i]=min(b[i],pg[i+1]);
	rep(i,1,n){
		if(pf[i-1]>pg[i+1]||i>pf[i-1]&&i<pg[i+1])continue;
		if(i<=pf[i-1])c[Mp(b[i],pf[i-1])]++;
		else c[Mp(pg[i+1],b[i])]++;
	}
	int ans=-2;
	for(auto i:c)ans=max(ans,i.se);
	printf("%d\n",ans+sum);
}
signed main(){
	int t=1;
		scanf("%d",&t);
	while(t--)
		Yorushika();
}