#include <bits/stdc++.h>
using namespace std;
// clang-format off
#define fi first
#define se second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (int32_t)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define left Kurumi_Tokisaki
#define right Kei_Karuizawa
#define next Mai_Sakurajima
#define div Yume_Irido
#define prev Chizuru_Mizuhara
#define cntbit(x) __builtin_popcountll(x)
#define MASK(x) ( 1ll << (x) )
#define Yes cout << "Yes"
#define YES cout << "YES"
#define No cout << "No"
#define NO cout << "NO"
#define AA cout << "Alice"
#define BB cout << "Bob"
/// TASK
/// -----------------------------
#ifdef LMQZZZ
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << " ]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define deb(x...) cerr << "[ in " <<__func__<< "() : line " <<__LINE__<< " ] : [ " << #x << " ] = [ "; _print(x); cerr << '\n';
#define TASK "C"
#else
#define deb(x...) 3326
#define TASK "C"
#endif
///------------------------------
void lmqzzz();
void init() {};
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(TASK ".inp", "r")) {
freopen(TASK ".inp", "r", stdin);
freopen(TASK ".out", "w", stdout);
}
/// =================================
constexpr bool MULTITEST = 0;
/// ================================
init();
int32_t TT = 1;
if ( MULTITEST ) cin >> TT;
for(int32_t TTT = 1; TTT <= TT; TTT ++) {
lmqzzz();
cout << '\n';
}
}
template <class T> inline T min(const T &a, const T &b, const T &c) { return min(a, min(b, c)); }
template <class T> inline T max(const T &a, const T &b, const T &c) { return max(a, max(b, c)); }
template <class T, class U> inline bool mini(T &a, const U &b) { if (a > b) { a = b; return 1; } return 0; }
template <class T, class U> inline bool maxi(T &a, const U &b) { if (a < b) { a = b; return 1; } return 0; }
constexpr int16_t dr[] = {0, 0, -1, 1};
constexpr int16_t dc[] = {1, -1, 0, 0};
constexpr int64_t MOD = 1e9 + 7;
constexpr int32_t MAXN = 1e6 + 10;
// clang-format on
class segtree_t {
public:
segtree_t *left, *right;
int l, r, m;
int64_t val, lazy;
segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1), val(0), lazy(0) {
if (l == r) return;
left = new segtree_t(l, m);
right = new segtree_t(m + 1, r);
}
void Update(int s, int t, int64_t x) {
if (r < s or l > t) return;
if (s <= l && r <= t) {
val += x;
lazy += x;
return;
}
Down();
left->Update(s, t, x);
right->Update(s, t, x);
Up();
}
int64_t Get(int s, int t) {
if (r < s or l > t) return -1e18;
if (s <= l && r <= t) return val;
Down();
return max(left->Get(s, t), right->Get(s, t));
}
void Up() {
val = max(left->val, right->val);
}
void Down() {
left->lazy += lazy;
right->lazy += lazy;
right->val += lazy;
left->val += lazy;
lazy = 0;
}
};
int n, m;
int a[MAXN];
int par[MAXN], l[MAXN], r[MAXN];
int x[MAXN], y[MAXN], c[MAXN], o[MAXN];
vector<int> building[MAXN];
vector<pair<int, int>> star[MAXN], star_col[MAXN];
int root(int u) {
return par[u] < 0 ? u : par[u] = root(par[u]);
}
void unite(int u, int v) {
u = root(u), v = root(v);
if (par[u] > par[v]) swap(u, v);
par[u] += par[v];
par[v] = u;
l[u] = min(l[u], l[v]);
r[u] = max(r[u], r[v]);
}
void lmqzzz() {
cin >> n;
for (int i = 1; i <= n; i++) par[i] = -1, l[i] = r[i] = i;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) building[a[i]].emplace_back(i);
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> x[i] >> y[i] >> c[i];
star_col[x[i]].emplace_back(y[i], c[i]);
}
for (int i = 1; i <= n; i++) {
sort(star_col[i].begin(), star_col[i].end());
vector<pair<int, int>> tmp;
int last = 0;
for (auto [y, c] : star_col[i]) {
if (tmp.size() && tmp.back().second >= c) continue;
tmp.emplace_back(y, c);
star[y].emplace_back(i, c - last);
last = c;
}
}
segtree_t *tree = new segtree_t(1, n);
for (int i = 1; i <= n; i++) {
for (auto [j, c] : star[i]) {
tree->Update(j, j, c);
}
for (int j : building[i]) {
int64_t L = 0, R = 0;
if (o[j - 1]) {
int x = root(j - 1);
L = tree->Get(l[x], r[x]);
}
if (o[j + 1]) {
int x = root(j + 1);
R = tree->Get(l[x], r[x]);
}
if (o[j - 1]) {
int x = root(j - 1);
tree->Update(l[x], r[x], R);
unite(j, j - 1);
}
if (o[j + 1]) {
int x = root(j + 1);
tree->Update(l[x], r[x], L);
unite(j, j + 1);
}
o[j] = 1;
tree->Update(j, j, L + R);
}
}
cout << accumulate(c + 1, c + m + 1, 0ll) - tree->val;
}
