#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+5;
int t,n,m;
int f[N][30];
int a[N];
map<int ,ll> q;
int read()
{
	int res=0;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		res=10*res+c-'0';
		c=getchar();
	}
	return res;
}
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);
//	}
//	
//}
ll find2(int l,int r,int p)
{
	if(p==m)
	{
		if(!l&&!r)
		{
			return ask(w[p].l,w[p].r );
		}
		ll ans1=ask(l,w[p].l)+ask(r,w[p].r);
		ll 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)
	{
		ll ans1=ask(l,w[p].l)+ask(r,w[p].r);
		ll ans2=ask(w[p].l,r);
		return min(ans1,ans2)+find2(0,0,p+1);
	}
	if(w[p+1].l>r)
	{
		return ask(l,r)+find2(r,w[p].r,p+1);
	}
	ll ans1=ask(l,r)+find2(r,w[p].r,p+1);
	ll ans2=find2(w[p].l,r,p+1);
	ll 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();
		n=read();
		for(int i=1;i<=n;i++)
		{
			a[i]=read();
		}
		yuchuli();
		m=read();
		for(int i=1;i<=m;i++)
		{
			w[i].l=read();
			w[i].r=read();
		}
		//a[n+1]=0;
		//w[m+1].l=w[m+1].r=n+1;
		ll ans=find2(0,0,1);
		//cout<<ans<<endl;
		printf("%lld\n",ans);
	}
}