#include "bits/stdc++.h"
using namespace std;
#define s second
#define f first
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef vector<ll> vi;
#define FOR(i, a, b) for (ll i = (a); i<b; i++)
bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; }
bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; }
const ll N = 2e5 + 10;
const ll B = 20;
ll a[N];
pii sp[N][B];
vpii by_row[N];
pii rmq(ll l, ll r) {
r++; // exclusive
ll d = floor(log2(r - l));
return max(sp[l][d], sp[r-(1 << d)][d]);
}
void ins(pair<map<ll, ll>, ll> &obj, pii x) {
map<ll, ll>& m = obj.f;
auto it = m.upper_bound(x.f);
if (it != m.begin()) {
auto bef = prev(it, 1);
if ((*bef).s + obj.s >= x.s) return;
}
while (it != m.end() && (*it).s + obj.s <= x.s) {
it=next(it, 1);
m.erase(prev(it, 1));
}
m[x.f]=x.s - obj.s;
}
pair<map<ll, ll>, ll> solve(ll l, ll r) {
if (l > r) return {};
if (r == l) {
pair<map<ll, ll>, ll> res;
for (auto x: by_row[l]) ins(res, x);
return res;
}
ll cur = rmq(l, r).s;
auto le = solve(l, cur-1);
auto ri = solve(cur+1, r);
ll bestl = 0;
auto it = le.f.begin();
while (it != le.f.end() && (*it).f <= a[cur]) {
bestl=max(bestl, (*it).s + le.s);
it = next(it, 1);
le.f.erase(prev(it, 1));
}
it = ri.f.begin();
ll bestr = 0;
while (it != ri.f.end() && (*it).f <= a[cur]) {
bestr=max(bestr, (*it).s + ri.s);
it = next(it, 1);
ri.f.erase(prev(it, 1));
}
pair<map<ll, ll>, ll> res;
res.f[a[cur]]=bestr + bestl;
for (auto x: by_row[cur]) ins(res, {x.f, x.s + bestr + bestl});
ri.s += bestl;
le.s += bestr;
if (res.f.size() < le.f.size()) swap(res, le);
for (auto x: le.f) ins(res, {x.f, x.s + le.s});
if (res.f.size() < ri.f.size()) swap(res, ri);
for (auto x: ri.f) ins(res, {x.f, x.s + ri.s});
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n;
cin >> n;
FOR(i, 1, n+1) {
cin >> a[i];
sp[i][0]={a[i], i};
}
FOR(j, 1, B) {
FOR(i, 1, n+1) {
sp[i][j] = max(sp[i][j-1], sp[min(i + (1 << (j-1)), N-1)][j-1]);
}
}
ll s;
cin >> s;
ll sm = 0;
FOR(_, 0, s) {
ll x, y, c;
cin >> x >> y >> c;
sm += c;
by_row[x].pb({y, c});
}
auto res = solve(1, n);
ll best = 0;
for (auto x: res.f) {
best = max(best, x.s + res.s);
}
cout << sm-best << endl;
}
