// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
#define mp make_pair
#define f first
#define s second
using ll = long long;
template<class T> using V = vector<T>;
template<class T, size_t SZ> using AR = array<T, SZ>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
using vl = V<ll>;
const int INF = 1e9 + 10;
struct BIT {
vl data; int N; void init(int n) { N = n; data = vl(N); }
void add(int p, ll x) { for(++p;p<=N;p+=p&-p) data[p - 1] += x; }
void add(int l, int r, ll x) { add(l, +x); add(r + 1, -x); }
ll get(int r) { ll s = 0; for(++r;r;r-=r&-r) s += data[r - 1]; return s; }
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int N; cin >> N;
vi A(N + 2, INF); for(int i = 1; i <= N; i++) cin >> A[i];
BIT B; B.init(N + 2);
// stack solves all problems
// including cancer (impl)
int M; cin >> M;
vl C(M);
V<vpi> E(N + 2); ll all = 0;
for(int _ = 0; _ < M; _++) {
int i, h; cin >> i >> h >> C[_];
all += C[_];
E[i].pb(mp(h, _));
}
V<vpi> nxt(N + 2); int cur = 0;
V<V<AR<int, 3>>> in;
set<AR<int, 3>> S;
auto add = [&](int lx, int rx) {
nxt[lx].pb(mp(rx, cur));
++cur; in.pb({});
int h = min(A[lx], A[rx]);
while(sz(S) && (*begin(S))[0] <= h) {
in.back().pb(*begin(S));
S.erase(begin(S));
}
};
vi stk = {0};
for(int i = 1; i <= N + 1; i++) {
while(stk.back() != 0 && A[stk.back()] <= A[i]) {
add(stk.back(), i); stk.pop_back();
}
add(stk.back(), i); stk.pb(i);
for(auto& [h, idx] : E[i]) {
S.insert({h, i, idx});
}
}
function<ll(int, int, int)> dnc = [&](int l, int r, int i) {
// cout << l << " " << r << " " << i << endl;
if (r - l <= 1) return 0LL;
int lx = l, rx = -1, ix = -1;
vpi div; vl res;
do {
tie(rx, ix) = nxt[lx].back(); nxt[lx].pop_back();
// cout << "===> " << lx << " " << rx << " " << ix << endl;
res.pb(dnc(lx, rx, ix));
div.pb(mp(lx, rx));
lx = rx;
} while(rx != r);
int m = sz(res);
ll bst = accumulate(begin(res), end(res), 0LL);
for(int i = 0; i < m; i++) {
auto [lx, rx] = div[i];
// cout << "ADDED: " << l << " " << lx << " - " << rx << " " << r << endl;
B.add(l + 1, lx, res[i]); B.add(rx, r - 1, res[i]);
}
// cout << l << " " << r << " -> " << i << endl;
// cout << "ANS: " << bst << endl;
for(auto& [h, pos, idx] : in[i]) {
// cout << "STAR: " << pos << " " << h;
// cout << " -> " << B.get(pos) << " " << C[idx] << endl;
ll ans = B.get(pos) + C[idx];
bst = max(bst, ans);
}
// cout << l << " " << r << " << i << " ----> " << bst << endl;
return bst;
};
nxt[0].pop_back();
cout << all - dnc(0, N + 1, cur - 1) << nl;
exit(0-0);
}
