#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
#define int long long
#define fi first
#define se second
const int N = 2e5 + 5;
int n, m, a[N], ls[N << 6], rs[N << 6], lc[N], rc[N], rt[N];
int rw[N], cl[N], cost[N];
int node = 0;
int seg[N << 6], lazy[N << 6];
// i <= v: max(x <= v dp[x][j] + j <= v dp[y][j])
// all: dp[u][i] = max(dp[x][i], j <= v dp[y][j]
// pt update: dp[u][h] = max(x <= v dp[x][j] + j <= v dp[y][j]) + c (can do in O(log n)) per
// range add, range maxmerge, all assign, range maxquery
void push(int id) {
if (!id) return;
seg[id] += lazy[id];
if (lazy[id]) {
if (ls[id]) lazy[ls[id]] += lazy[id], seg[ls[id]] += lazy[id];
if (rs[id]) lazy[rs[id]] += lazy[id], seg[rs[id]] += lazy[id];
}
lazy[id] = 0;
}
void insert_value(int& root, int pos, int value, int l, int r) {
if (!root) root = ++node;
seg[root] = max(seg[root], value);
// debug("modified", root, l, r, value);
if (l == r) return;
int mid = (l + r) / 2;
if (pos <= mid) insert_value(ls[root], pos, value, l, mid);
else insert_value(rs[root], pos, value, mid + 1, r);
}
void range_add_update(int root, int ql, int qr, int v, int l, int r) {
push(root);
if (!root || qr < l || r < ql) return;
if (ql <= l && r <= qr) {
lazy[root] = v;
push(root);
return;
}
int mid = (l + r) / 2;
range_add_update(root, ql, qr, v, l, mid);
range_add_update(root, ql, qr, v, mid + 1, r);
seg[root] = max(seg[ls[root]], seg[rs[root]]);
}
int range_max_query(int root, int ql, int qr, int l, int r) {
push(root);
if (!root || qr < l || r < ql) return 0;
if (ql <= l && r <= qr) {
// debug("maxed", root, l, r, seg[root]);
return seg[root];
}
int mid = (l + r) / 2;
return max(range_max_query(ls[root], ql, qr, l, mid), range_max_query(rs[root], ql, qr, mid + 1, r));
}
int merge(int root, int x, int y) {
push(root), push(x), push(y);
if (!x || !y) return x + y;
if (!root) root = ++node;
seg[root] = max(seg[x], seg[y]);
ls[root] = merge(ls[root], ls[x], ls[y]);
rs[root] = merge(rs[root], rs[x], rs[y]);
return root;
}
vector<pair<int, int>> star[N];
void process(int u, int x, int y) {
// debug(u, x, y);
int valx = range_max_query(rt[x], 1, a[u], 1, n);
// debug("hi");
int valy = range_max_query(rt[y], 1, a[u], 1, n);
// debug("hi");
range_add_update(rt[x], 1, n, valy, 1, n);
// debug("hi");
range_add_update(rt[y], 1, n, valx, 1, n);
// debug()
// for (auto& [r, c] : star[u]) insert_value(rt[u], r, c, 1, n);
// debug("hi");
rt[u] = merge(rt[u], rt[x], rt[y]);
// for (int i = 1; i <= n; i++) {
// debug("heya!");
// debug(range_max_query(rt[u], i, i, 1, n));
// }
// debug("hi");
for (auto& [r, c] : star[u]) {
// debug("insert", u, r, c);
insert_value(rt[u], r, valx + valy + c, 1, n);
}
}
void solve() {
int sum = 0;
cin >> n;
vector<int> idx;
for (int i = 1; i <= n; i++) {
cin >> a[i];
idx.push_back(i);
}
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> rw[i] >> cl[i] >> cost[i];
star[rw[i]].push_back({cl[i], cost[i]});
sum += cost[i];
}
sort(idx.begin(), idx.end(), [&] (int x, int y) { return make_pair(a[x], x) < make_pair(a[y], y); });
stack<pair<int, int>> st;
vector<int> lst(n+1, -1), nxt(n+1, -1);
for (int i = 1; i <= n; i++) {
while (!st.empty() && st.top() < make_pair(a[i], i)) st.pop();
if (!st.empty()) lst[i] = st.top().second;
st.push({a[i], i});
}
while (!st.empty()) st.pop();
for (int i = n; i >= 1; i--) {
while (!st.empty() && st.top() < make_pair(a[i], i)) st.pop();
if (!st.empty()) nxt[i] = st.top().second;
st.push({a[i], i});
}
for (int i = 1; i <= n; i++) {
if (lst[i] == -1) lc[nxt[i]] = i;
else if (nxt[i] == -1) rc[lst[i]] = i;
else if (make_pair(a[lst[i]], lst[i]) < make_pair(a[nxt[i]], nxt[i])) rc[lst[i]] = i;
else lc[nxt[i]] = i;
}
for (auto i : idx) process(i, lc[i], rc[i]);
// debug(idx);
// for (int i = 1; i <= n; i++) debug(i, lc[i], rc[i]);
cout << sum - range_max_query(rt[idx.back()], 1, n, 1, n) << '\n';
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int test = 1;
// cin >> test;
while (test--) solve();
}
