#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<int ,int> q;
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(p==m+1)
//	{
//		return ask(l,r);
//	}
//	if(r<w[p].l)
//	{
//		return ask(l,r)+find1(w[p].l,w[p].r,p+1);
//	}
//	if(w[p].l>=l&&w[p].r<=r)
//	{
//		return find1(w[p].l,w[p].r,p+1);
//	}
//	
//}
int find2(int l,int r,int p)
{
	if(p==m)
	{
		if(!l&&!r)
		{
			return ask(w[p].l,w[p].r );
		}
		int ans1=ask(l,w[p].l)+ask(r,w[p].r);
		int ans2=ask(w[p].l,r);
		return min(ans1,ans2);
	}
	if(r<w[p].l)
	{
		if(q[p])
		{
			return q[p];
		}
		int num=ask(l,r);
		if(w[p+1].l>w[p].r)
		{
			if(!l&&!r)
			{
				return q[p]=ask(w[p].l,w[p].r)+find2(0,0,p+1);
			}
			return ask(l,r)+ask(w[p].l,w[p].r)+find2(0,0,p+1);
		}
		if(!l&&!r)
		{
			return q[p]=find2(w[p].l,w[p].r,p+1);
		}
		return ask(l,r)+find2(w[p].l,w[p].r,p+1);
	}
	if(w[p].l>=l&&w[p].r<=r)
	{
		if(w[p+1].l>w[p].r)
		{
			return  ask(w[p].l,w[p].r)+find2(0,0,p+1);
		}
		return find2(w[p].l,w[p].r,p+1);
	}
	if(w[p+1].l>w[p].r)
	{
		int ans1=ask(l,w[p].l)+ask(r,w[p].r);
		int ans2=ask(w[p].l,r);
		return min(ans1,ans2)+find2(0,0,p+1);
	}
	int ans1=ask(l,r)+find2(r,w[p].r,p+1);
	int ans2=find2(w[p].l,r,p+1);
	int ans=min(ans1,ans2);
	return ans;
}
signed main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--)
	{
		q.clear();
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
		}
		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=find2(0,0,1);
		cout<<ans<<endl;
	}
}