#include <bits/stdc++.h>
#define int long long
using namespace std;
string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
bool first = true;
string res = "[";
for (const auto &x : v) {
if (!first)
res += ", ";
first = false;
res += to_string(x);
}
res += "]";
return res;
}
void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
cout << ' ' << to_string(H);
dbg_out(T...);
}
#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
template <class T> struct RMQ {
vector<vector<T>> jmp;
RMQ(const vector<T> &V) : jmp(1, V) {
for (int pw = 1, k = 1; pw * 2 <= (int)V.size(); pw *= 2, ++k) {
jmp.emplace_back((int)V.size() - pw * 2 + 1);
for (int j = 0; j < (int)jmp[k].size(); ++j)
jmp[k][j] = max(jmp[k - 1][j], jmp[k - 1][j + pw]);
}
}
T query(int a, int b) { // [a, b)
assert(a < b);
int dep = 31 - __builtin_clz(b - a);
return max(jmp[dep][a], jmp[dep][b - (1 << dep)]);
}
};
template <class T> class Fenwick {
public:
int lim;
vector<T> bit;
Fenwick(int n) : lim(n + 1), bit(lim) {}
void upd(int pos, T val) {
for (pos++; pos < lim; pos += pos & -pos)
bit[pos] += val;
}
T sum(int r) { // < r
T ret = 0;
for (; r; r -= r & -r)
ret += bit[r];
return ret;
}
T sum(int l, int r) { // [l, r)
return sum(r) - sum(l);
}
void rangeAdd(int deb, int fin, int x) { // [deb, fin)
dbg(deb, fin, x);
upd(deb, x);
upd(fin, -x);
}
int point(int pos) { return sum(pos + 1); }
};
template <class T> using min_pq = priority_queue<T, vector<T>, greater<T>>;
signed main(void) {
ios_base::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
vector<int> height(N);
for (int &x : height)
cin >> x;
vector<pair<int, int>> toRMQ;
for (int i = 0; i < N; ++i)
toRMQ.emplace_back(height[i], i);
RMQ rmq(toRMQ);
vector<vector<pair<int, int>>> onPos(N);
int nbEtoiles;
cin >> nbEtoiles;
int totCost = 0;
for (int i = 0; i < nbEtoiles; ++i) {
int x, y, c;
cin >> x >> y >> c;
totCost += c;
onPos[x - 1].emplace_back(y, c);
}
Fenwick<int> fen(N);
auto DFS = [&](auto dfs, int deb, int fin,
int prevHeight) -> pair<min_pq<tuple<int, int, int>>, int> {
auto [valMax, posMax] = rmq.query(deb, fin);
min_pq<tuple<int, int, int>> toProcess;
for (auto [y, c] : onPos[posMax])
toProcess.emplace(y, posMax, c);
int solFree = 0;
int addL = 0, addR = 0;
if (deb < posMax) {
auto [toAdd, freeL] = dfs(dfs, deb, posMax, valMax);
while (!toAdd.empty()) {
toProcess.emplace(toAdd.top());
toAdd.pop();
}
addL = freeL;
solFree += freeL;
}
if (posMax + 1 < fin) {
auto [toAdd, freeR] = dfs(dfs, posMax + 1, fin, valMax);
while (!toAdd.empty()) {
toProcess.emplace(toAdd.top());
toAdd.pop();
}
addR = freeR;
solFree += freeR;
}
fen.rangeAdd(posMax, fin, addL);
fen.rangeAdd(deb, posMax + 1, addR);
while (!toProcess.empty() and get<0>(toProcess.top()) <= prevHeight) {
auto [y, x, c] = toProcess.top();
toProcess.pop();
int gain = c + fen.point(x);
dbg(x, y, gain, fen.point(x));
solFree = max(solFree, gain);
}
dbg(deb, fin, solFree);
return pair(toProcess, solFree);
};
cout << totCost - DFS(DFS, 0, N, 1e18).second << endl;
}
