#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200'000;
const int M = 20;
const int S = 2 * N;
const ll INF = 1'000'000'000'000'000;
int n, m, a[N + 10], mx[N + 10][M + 5];
int counter, tMark, mark[N + 10];
ll seg[4 * N + 10], dp[S + 10];
ll lazyAdd[4 * N + 10], lazyMax[4 * N + 10];
vector<pair<int, ll>> vec[N + 10], res[S + 10];
ll sum;
void readInput() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
cin >> m;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
ll c;
cin >> c;
sum += c;
vec[x].push_back({y, c});
}
}
void shift(int, int, int);
ll get(int st, int en, int id = 1, int l = 1, int r = n + 1) {
if (en <= l || r <= st)
return -INF;
if (st <= l && r <= en)
return seg[id];
shift(id, l, r);
int mid = (l + r) >> 1;
return max(get(st, en, id << 1, l, mid), get(st, en, id << 1 | 1, mid, r));
}
void update(int st, int en, ll val, ll mx, int id = 1, int l = 1, int r = n + 1) {
if (en <= l || r <= st)
return;
if (st <= l && r <= en) {
seg[id] += val;
lazyAdd[id] += val;
lazyMax[id] += val;
seg[id] = max(seg[id], mx);
lazyMax[id] = max(lazyMax[id], mx);
return;
}
shift(id, l, r);
int mid = (l + r) >> 1;
update(st, en, val, mx, id << 1, l, mid);
update(st, en, val, mx, id << 1 | 1, mid, r);
seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}
void shift(int id, int l, int r) {
if (!lazyAdd[id] && lazyMax[id] == -1)
return;
int mid = (l + r) >> 1;
update(l, r, lazyAdd[id], lazyMax[id], id << 1, l, mid);
update(l, r, lazyAdd[id], lazyMax[id], id << 1 | 1, mid, r);
lazyAdd[id] = 0;
lazyMax[id] = -1;
}
void calcMax() {
for (int i = 1; i <= n; i++)
mx[i][0] = i;
for (int j = 1; j <= M; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
if (a[mx[i][j - 1]] <= a[mx[i + (1 << (j - 1))][j - 1]])
mx[i][j] = mx[i + (1 << (j - 1))][j - 1];
else
mx[i][j] = mx[i][j - 1];
}
int getMax(int l, int r) {
int lg = 31 - __builtin_clz(r - l + 1);
return a[mx[l][lg]] <= a[mx[r - (1 << lg) + 1][lg]]? mx[r - (1 << lg) + 1][lg]: mx[l][lg];
}
void calcVec() {
for (int i = 1; i <= n; i++)
sort(vec[i].begin(), vec[i].end());
}
void solveOneCell(int id, int l, int r, int last) {
for (auto [idx, val]: vec[l])
update(idx, n + 1, 0, val);
dp[id] = get(1, last + 1);
//cout << l << ' ' << r << ' ' << last << ": " << dp[id] << endl;
}
void defaltSeg() {
update(1, n + 1, -INF, 0);
}
void checkKeep(int id, int l, int r, bool keep) {
if (keep == true)
return;
tMark++;
for (int pnt = l; pnt <= r; pnt++)
for (auto [idx, val]: vec[pnt])
if (mark[idx] != tMark) {
mark[idx] = tMark;
res[id].push_back({idx, get(1, idx + 1)});
}
sort(res[id].begin(), res[id].end());
defaltSeg();
}
void changeSeg(int id, int mid, int l, int r) {
update(a[mid], n + 1, dp[l], 0);
for (auto [idx, val]: res[l])
update(idx, n + 1, 0, dp[r] + val);
for (auto [idx, val]: vec[mid])
update(idx, n + 1, 0, dp[l] + dp[r] + val);
}
int getLen(pair<int, int> p) {
return p.second - p.first + 1;
}
int solve(int l = 1, int r = n, int last = n, bool keep = true) {
if (r < l)
return 0;
int id = ++counter;
if (l == r) {
solveOneCell(id, l, r, last);
checkKeep(id, l, r, keep);
return id;
}
int mid = getMax(l, r);
pair<int, int> p[2] = {{l, mid - 1}, {mid + 1, r}};
if (getLen(p[0]) > getLen(p[1]))
swap(p[0], p[1]);
int lft = solve(p[0].first, p[0].second, a[mid], false);
int rght = solve(p[1].first, p[1].second, a[mid], true);
changeSeg(id, mid, lft, rght);
dp[id] = get(1, last + 1);
checkKeep(id, l, r, keep);
return id;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
readInput();
calcMax();
calcVec();
cout << sum - dp[solve()] << flush;
return 0;
}
