#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MA 1200000
int n,q;
int o[MA];
struct ASK{
	int l,r;
}ak[MA];
int lr[MA][2],lrtop;
int L[MA],R[MA];
int tree[4000000],lazy[4000000];
bool cmp(ASK x,ASK y){
	return (x.l==y.l)? (x.r>y.r):(x.l<y.l);
}
void add_lr(int l,int r){
	lrtop++;
	lr[lrtop][0]=l;
	lr[lrtop][1]=r;
}
void init(){
	int zz=ak[1].r;
	add_lr(ak[1].l,ak[1].r);
	for(int i=2;i<=q;i++){
		if(ak[i].r>zz){
			zz=ak[i].r;
			add_lr(ak[i].l,ak[i].r);
		}
	}
	zz=1;
	for(int i=1;i<=n;i++){
		while(zz<lrtop&&lr[zz][1]<i)zz++;
		L[i]=zz;
	}
	zz=lrtop;
	for(int i=n;i;i--){
		while(zz>1&&lr[zz][0]>i)zz--;
		R[i]=zz;
	}
}
void add(int l,int r,int k,int x,int y){
	if(x<=l&&r<=y){tree[k]++;lazy[k]++;return ;}
	int mid=(l+r)>>1;
	if(x<=mid)add(l,mid,k<<1,x,y);
	if(y>mid)add(mid+1,r,k<<1|1,x,y);
	tree[k]=lazy[k]+max(tree[k<<1],tree[k<<1|1]);
	return ;
}
int ask(int l,int r,int k,int x,int y){
	if(x<=l&&r<=y)return tree[k];
	int mid=(l+r)>>1,RE=0;
	if(x<=mid)RE=max(RE,ask(l,mid,k<<1,x,y));
	if(y>mid)RE=max(RE,ask(mid+1,r,k<<1|1,x,y));
	return RE+lazy[k];
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%lld",&o[i]);
	}
	cin>>q;
	for(int i=1;i<=q;i++){
		scanf("%lld%lld",&ak[i].l,&ak[i].r);
	}
	sort(ak+1,ak+1+q,cmp);
	init();
	for(int i=1;i<=n;i++){
		ak[i].l=o[i];
		ak[i].r=i;
	}
	sort(ak+1,ak+1+n,cmp);
	int ans=0;
	for(int i=n;i;i--){
		int zz=ak[i].r;
		if(L[zz]>R[zz])continue;
		ans=max(ans,ak[i].l*ask(1,n,1,L[zz],R[zz]));
		add(1,n,1,L[zz],R[zz]);
	}
	cout<<ans<<endl;
}