WA on #2求调

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
const int M=5e5+5;
int T,n,m,a[M],q[M],pre[M];
int dp[M];
void solve()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]),pre[i]=0;a[++n]=0;
	scanf("%lld",&m);
	for(int i=1;i<=m;++i)
	{
		int l,r;
		scanf("%lld%lld",&l,&r);
		pre[r+1]=max(pre[r+1],l);
	}
	pre[1]=0;
	for(int i=2;i<=n;++i) pre[i]=max(pre[i],pre[i-1]);
	int l=1,r=1;q[0]=0;
	for(int i=1;i<=n;++i)
	{
		while(l<=r&&q[l]<pre[i]) l++;
		dp[i]=dp[q[l]]+a[i];
		while(l<=r&&dp[q[r]]>=dp[i]) r--;
		q[++r]=i;
	}
	printf("%lld\n",dp[n]);
	return;
}
signed main()
{
	// freopen("data2.in","r",stdin);
	// freopen("answer.out","w",stdout);
	scanf("%lld",&T);
	while(T--) solve();
	return 0;
}