c o d e code code

#include
#include
#include
#include
using namespace std;
const int N=1e5+10,K=300;
int T,n,a[N],maxs[N],mins[N];
int cnt,b[K],e[K],z[K];
bool f[2][N];
stack<int> q1,q2;
int main()
{
	//freopen("sample2.in","r",stdin);
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			maxs[i]=max(maxs[i-1],a[i]);
		}
		mins[n+1]=2147483647/3;cnt=0;
		for(int i=n;i>=1;i--)
			mins[i]=min(mins[i+1],a[i]);
		for(int i=1;i<=n;i++)
			if(maxs[i]<=mins[i+1]||i==n)
				b[++cnt]=e[cnt-1]+1,e[cnt]=i;
		bool flag=0;
		for(int i=1;i<=cnt;i++){
			while(!q1.empty())q1.pop();
			while(!q2.empty())q2.pop(); 
			for(int j=b[i];j<=e[i];j++){
				if(q1.empty()||a[j]>q1.top())q1.push(a[j]);
				else if(q2.empty()||a[j]>q2.top())q2.push(a[j]);
				else{flag=1;break;}
			}
			if(flag)break;
			z[i]=q1.size()-q2.size();
		}
		if(flag){
			printf("-1
");
			continue;
		}
		memset(f,0,sizeof(f));
		f[0][0]=1;
		for(int i=1;i<=cnt;i++)
			for(int j=0;j<=n;j++)
				f[i&1][j]=f[~i&1][abs(j-z[i])]|f[~i&1][abs(j+z[i])];
		for(int j=0;j<=n;j++)
			if(f[cnt&1][j]){
				printf("%d
",j);
				break;
			}
	}
}