#include <bits/stdc++.h>
using namespace std;

typedef int uci;
typedef long long ll;
#define int long long
#define F first
#define S second
#define ar array

int n;

void update(int v, int val, int l, int r, int lq, int rq, vector<ar<int, 2>> &seg){
    if(l > r || lq > r || rq < l)
        return;
    else if(lq <= l && r <= rq){
        seg[v][1] += val;
        seg[v][0] += val;
    }else{
        int mid = l + (r-l)/2;
        if(seg[v][1] != 0){
            update(v*2, seg[v][1], l, mid, l, mid, seg);
            update(v*2+1, seg[v][1], mid+1, r, mid+1, r, seg);
            seg[v][0] = max(seg[v*2][0], seg[v*2+1][0]);
            seg[v][1] = 0;
        }

        update(v*2, val, l, mid, lq, rq, seg);
        update(v*2+1, val, mid+1, r, lq, rq, seg);
    }
}

int query(int v, int l, int r, int lq, int rq, vector<ar<int, 2>> &seg){
    if(l > r || rq < l || lq > r)
        return 0;
    else if(lq <= l && r <= rq)
        return seg[v][0];
    else{
        int mid= l + (r-l)/2;
        if(seg[v][1] != 0){
            update(v*2, seg[v][1], l, mid, l, mid, seg);
            update(v*2+1, seg[v][1], mid+1, r, mid+1, r, seg);
            seg[v][0] = max(seg[v*2][0], seg[v*2+1][0]);
            seg[v][1] = 0;
        }
        return max(query(v*2, l, mid, lq, rq, seg), query(v*2+1, mid+1, r, lq, rq, seg));
    }
}

void solve(){
    cin >> n;
    vector<ar<int, 2>> a(n);
    for(int i{}; i < n; ++i){
        cin >> a[i][0];
        a[i][1] = i;
    }

    int m;
    cin >> m;
    vector<ar<int, 2>> b(m);
    for(int i{}; i < m; ++i){
        cin >> b[i][0] >> b[i][1];
        b[i][0]--, b[i][1]--;
    }
    sort(b.begin(), b.end(), [](auto a, auto b){
        return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
            });
    vector<ar<int, 2>> c;
    int furthest = -1;
    for(int i{}; i < m; ++i){
        if(b[i][1] > furthest)
            c.push_back(b[i]);
        furthest = max(furthest, c.back()[1]);
    }
    m = c.size();
    b.swap(c);

    vector<ar<int, 2>> seg(4*m);
    sort(a.rbegin(), a.rend());

    int out{};
    for(int i{}; i < n; ++i){
        int lb = m, rb{};
        int l = 0, r = m-1;
        while(l <= r){
            int mid = l + (r-l)/2;
            if(b[mid][0] <= a[i][1] && a[i][1] <= b[mid][1]){
                lb = mid;
                r = mid-1;
            }else{
                if(b[mid][1] < a[i][1])
                    l = mid+1;
                else
                    r = mid-1;
            }
        }
        l = 0, r = m-1;
        while(l <= r){
            int mid = l + (r-l)/2;
            if(b[mid][0] <= a[i][1] && a[i][1] <= b[mid][1]){
                rb = mid;
                l = mid+1;
            }else{
                if(b[mid][1] < a[i][1])
                    l = mid+1;
                else
                    r = mid-1;
            }
        }
        if(lb <= rb){
            int bb = query(1, 0, m-1, lb, rb, seg);
            out = max(out, a[i][0]*bb);
            update(1, 1, 0, m-1, lb, rb, seg);
        }
    }
    cout << out << '\n';
}

uci main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    solve();
}