/* Code by pp_orange */
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define m_p(a,b) make_pair(a,b)
#define pb push_back
#define ll long long
#define ull unsigned long long
#define ld long double
#define inf 0x7FFFFFFF
#define inff 9223372036854775807
#define rep(i,l,r) for(int i=l;i<r;++i)
#define repp(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r-1;i>=l;--i)
#define pper(i,r,l) for(int i=r;i>=l;--i)
#define pii pair<int,int>
#define fi first
#define se second
#define p_q priority_queue
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
#define lb(x) ((x)&-(x))
#define lg(x) (31^__builtin_clz(x))
#define vi vector<int>
#define vii vector<pii >
const int mod = 998244353;
//#define int ll
const int intsz = sizeof(int);
using namespace std;
inline int rd(){
	int x(0),f(1);char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}
inline void out(int X){
	if(X<0) {X=~(X-1); putchar('-');}
	if(X>9) out(X/10);
	putchar(X%10+'0');
}
ll pw(ll x,int d){
	ll t = 1;
	for(;d;d>>=1,x=x*x%mod)if(d&1)t = t*x%mod;
	return t;
}
#define MAX 1000005
#define mxv(x) tr[x].mxv
#define v(x) tr[x].v
struct Node{
	int v,mxv;
}tr[1<<21];
int a[MAX],b[MAX];
pii c[MAX];
int R[MAX];
void pushdown(int rt){
	mxv(ls(rt)) = max(mxv(ls(rt)),v(ls(rt))+mxv(rt));
	v(ls(rt)) += v(rt);
	mxv(rs(rt)) = max(mxv(rs(rt)),v(rs(rt))+mxv(rt));
	v(rs(rt)) += v(rt);
	mxv(rt) = 0;
	v(rt) = 0;
	return ;
}
void add(int lp,int rp,int l,int r,int vv,int rt){
	if(l<=lp&&rp<=r){
		v(rt) += vv;
		mxv(rt) = max(mxv(rt),v(rt));
		return ;
	}
	int mid = (lp+rp)>>1;
	pushdown(rt);
	if(l<=mid)add(lp,mid,l,r,vv,ls(rt));
	if(r>mid)add(mid+1,rp,l,r,vv,rs(rt));
	return ;
}
int ask(int lp,int rp,int pos,int rt){
	if(lp>=rp){
		return mxv(rt);
	}
	int mid = (lp+rp)>>1;
	pushdown(rt);
	if(pos<=mid)return ask(lp,mid,pos,ls(rt));
	return ask(mid+1,rp,pos,rs(rt));
}
void clr(int lp,int rp,int pos,int rt){
	if(lp>=rp){
		mxv(rt) = v(rt);
		return ;
	}
	int mid = (lp+rp)>>1;
	pushdown(rt);
	if(pos<=mid)clr(lp,mid,pos,ls(rt));
	else clr(mid+1,rp,pos,rs(rt));
	return ;
}
signed main(){
	//freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
	int n = rd();
	repp(i,1,n)a[i] = rd();
	repp(i,1,n)c[i] = {-a[i],i};
	sort(c+1,c+1+n);
	repp(i,1,n)b[c[i].se] = i;
	int q = rd();
	repp(i,1,q){
		int x = rd();
		int y = rd();
		R[x] = max(y,x);
	}
	repp(i,2,n)R[i] = max(R[i],R[i-1]);
	ll ans = 0;
	// cout<<"ok\n";
	repp(i,1,n){
		if(R[i]<i)continue;
		repp(j,max(i,R[i-1]+1),R[i]){
			clr(1,n,b[j],1);
			add(1,n,b[j],n,1,1);
		}
		ans = max(ans,a[i]*(ll)(ask(1,n,b[i],1)-1));
		// cout<<i<<" ask : "<<ask(1,n,b[i],1)<<endl;
		add(1,n,b[i],n,-1,1);
	}
	cout<<ans<<endl;
	return 0;
}