#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int t,n,m;
int f[N][30];
int a[N];
map<pair<int,int> ,int> q[N];
struct node
{
	int l,r;
}w[N];
void yuchuli()
{
	for(int i=1;i<=n;i++)
	{
		f[i][0]=a[i];
	}
	int p=log(n)/log(2);
	for(int j=1;j<=p;j++)
	{
		for(int i=1;i<=n-(1<<j)+1;i++)
		{
			f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
}
int ask(int l,int r)
{
	int p=log(r-l+1)/log(2);
	return min(f[l][p],f[r-(1<<p)+1][p]);
}
int find1(int l,int r,int p)
{
	if(q[p][make_pair(l,r)])
	{
		return q[p][make_pair(l,r)];
	}
	if(p==m+1)
	{
		return q[p][make_pair(l,r)]=ask(l,r);
	}
	if(r<w[p].l)
	{
		return q[p][make_pair(l,r)]=ask(l,r)+find1(w[p].l,w[p].r,p+1);
	}
	if(w[p].l>=l&&w[p].r<=r)
	{
		return q[p][make_pair(l,r)]=find1(w[p].l,w[p].r,p+1);
	}
	int ans1=ask(l,r)+find1(w[p].l,w[p].r,p+1);
	//int ans2=ask(w[p].l,w[p].r)+find1(l,r,p+1);
	int ans3=find1(w[p].l,r,p+1);
	int ans=min(ans1,ans3);
	return q[p][make_pair(l,r)]=ans;
}
signed main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			q[i].clear();
		}
		yuchuli();
		cin>>m;
		for(int i=1;i<=m;i++)
		{
			cin>>w[i].l>>w[i].r;
		}
		a[n+1]=0;
		w[m+1].l=w[m+1].r=n+1;
		int ans=find1(0,0,1);
		cout<<ans<<endl;
	}
}