#include <bits/stdc++.h>

struct Seg {
    int l, r;
};

struct CmpL {
    bool operator()(const Seg& a, const Seg& b) const { return a.l < b.l; }
};

struct CmpR {
    bool operator()(const Seg& a, const Seg& b) const { return a.r < b.r; }
};

struct CmpLR {
    bool operator()(const Seg& a, const Seg& b) const {
        if (a.l != b.l) { return a.l < b.l; }
        return a.r < b.r;
    }
};

const int N = 1e6 + 10;

struct Point {
    int p, x;
};

struct CmpX {
    bool operator()(const Point& a, const Point& b) const { return a.x < b.x; }
};

std::vector<Point> a;
std::vector<Seg> v;


void Input() {
    std::ios::sync_with_stdio(false);
    int n;
    std::cin >> n;
    for (int i = 1; i <= n; i++) { 
        int x;
        std::cin >> x;
        a.push_back((Point){i, x});
    }
    std::sort(a.begin(), a.end(), CmpX());
    std::reverse(a.begin(), a.end());
    int m;
    std::cin >> m;
    std::vector<Seg> w(m);
    for (auto& [l, r]: w) {
        std::cin >> l >> r;
    }
    std::sort(w.begin(), w.end(), CmpLR());
    for (const auto& s: w) {
        if (!v.empty()) {
            auto vb = v.back();
            if (vb.r >= s.r) { continue; }
            if (vb.l == s.l && vb.r <= s.r) { v.pop_back(); }
        }
        v.push_back(s);
    }
}

namespace ST {
    int son[N][2];
    int v[N], lazy[N];
    int nodeCount;
    void SolveLazy(int t) {
        int l = lazy[t];
        lazy[t] = 0;
        if (l == 0) { return; }
        v[t] += l;
        if (son[t][0] == 0) { return;}
        lazy[son[t][0]] += l;
        lazy[son[t][1]] += l;
    }

    void Refresh(int t) {
        SolveLazy(son[t][0]);
        SolveLazy(son[t][1]);
        v[t] = std::max(v[son[t][0]], v[son[t][1]]);
    }

    void Update(int t, int l, int r, int x, int L, int R) {
        if (l == L && r == R) {
            lazy[t] += x;
            return;
        }
        SolveLazy(t);
        int mm = L + (R - L) / 2;
        if (r <= mm) {
            Update(son[t][0], l, r, x, L, mm);
        } else if (l > mm) {
            Update(son[t][1], l, r, x, mm + 1, R);
        } else {
            Update(son[t][0], l, mm, x, L, mm);
            Update(son[t][1], mm + 1, r, x, mm + 1, R);
        }
        Refresh(t);
    }

    int QueryMax(int t, int l, int r, int L, int R) {
        SolveLazy(t);
        if (l == L && r == R) { return v[t]; }
        
        int mm = L + (R - L) / 2;
        if (r <= mm) { return QueryMax(son[t][0], l, r, L, mm); }
        if (l > mm) { return QueryMax(son[t][1], l, r, mm + 1, R); }
        return std::max(
            QueryMax(son[t][0], l, mm, L, mm),
            QueryMax(son[t][1], mm + 1, r, mm + 1, R)
        );
    }

    int Build(int L, int R) {
        int t = ++nodeCount;
        if (L == R) { return t; }
        int mm = L + (R - L) / 2;
        son[t][0] = Build(L, mm);
        son[t][1] = Build(mm + 1, R);
        return t;
    }
}

int GetL(int p) {
    auto it = std::lower_bound(v.begin(), v.end(), (Seg) {p,p}, CmpR());
    return it - v.begin();
}

int GetR(int p) {
    auto it = std::upper_bound(v.begin(), v.end(), (Seg) {p,p}, CmpL());
    if (it == v.begin()) { return -1; }
    return it - v.begin() - 1;
}

using ll = long long;

void Solve() {
    int L = 0, R = v.size() - 1;
    int t = 1;
    ST::Build(L, R);
    ll ans = 0;
    for (auto [p, x]: a) {
        int l = GetL(p);
        int r = GetR(p);
        if (l > r) { continue; }
        // std::cout << p << " ";
        // std::cout << x << " ";
        // std::cout << l << " ";
        // std::cout << r << std::endl;
        int count = ST::QueryMax(1, l, r, L, R);
        ans = std::max(ans, 1ll * x * count);
        ST::Update(1, l, r, 1, L, R);
    }
    std::cout << ans << std::endl;
}

int main() {
    Input();
    Solve();
}