#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5, maxN = 4e5 + 5, INF = 1e18;
struct range {
int l, r;
bool operator < (const range &b) const {
if (r - l != b.r - b.l) return r - l < b.r - b.l;
if (l != b.l) return l < b.l;
return r < b.r;
}
bool operator == (const range &b) const {
return (l == b.l && r == b.r);
}
};
struct node {
int x, y, c;
bool operator < (const node &b) const {
if (y!=b.y) return y < b.y;
if (x!=b.x) return x < b.x;
return c < b.c;
}
};
vector<node> star;
int dc1(node x) {return lower_bound(star.begin(), star.end(), x) - star.begin();}
vector<range> ranges;
int dc2(range x) {return lower_bound(ranges.begin(), ranges.end(), x) - ranges.begin();}
int sum[maxn];
vector<pair<int,int>> sub[maxn];
int ansR[maxn], ansS[maxN];
int worth(int x, int y, int R) {
int val = sum[R];
auto [l, r] = *prev(upper_bound(sub[R].begin(), sub[R].end(), make_pair(x, INF)));
if (l <= x && x <= r) {
int ID = dc2({l, r});
val -= ansR[ID];
val += worth(x, y, ID);
// if (x == 5 && y == 8) cout << "test " << ansS[dc1({x, A[x]+1, 0})] << endl;
// cout << "Test " << x << " " << A[x]+1 << " " << 0 << " " << ansS[dc1({x, A[x]+1, 0})] << endl;
}
return val;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
pair<int,int> a[n+1];
int A[n+1];
for (int i=1;i<=n;i++) {
cin >> a[i].first;
a[i].second = i;
A[i] = a[i].first;
}
sort(a+1, a+n+1);
int m, SUM = 0;
cin >> m;
for (int i=1;i<=m;i++) {
int x, y, c;
cin >> x >> y >> c;
star.push_back({x, y, c});
SUM += c;
}
for (int i=1;i<=n;i++) star.push_back({a[i].second, a[i].first + 1, 0});
set<int> s;
for (int i=0;i<=n+1;i++) s.insert(i);
int last = 1;
for (int i=1;i<=n;i++) {
for (; a[last].first < a[i].first; last++) {
auto it = s.upper_bound(a[last].second);
ranges.push_back({*prev(it) + 1, *it - 1});
// cout << "1 " << a[last].second << " " << ranges.back().first << " " << ranges.back().second << endl;
}
s.erase(a[i].second);
}
for (; last<=n; last++) {
auto it = s.upper_bound(a[last].second);
ranges.push_back({*prev(it) + 1, *it - 1});
// cout << "2 " << a[last].second << " " << ranges.back().first << " " << ranges.back().second << endl;
}
sort(ranges.begin(), ranges.end()); ranges.erase(unique(ranges.begin(), ranges.end()), ranges.end());
int sz = ranges.size();
sort(star.begin(), star.end());
vector<node> mem[sz];
for (int i=0;i<sz;i++) sub[i] = {{0, 0}, {ranges[i].l, -1}};
for (int i=1;i<=n;i++) s.insert(i);
last = 1;
for (auto [x, y, c]:star) {
// cout << x << " " << y << " " << c << endl;
for (;last <= n && a[last].first < y; last++) s.erase(a[last].second);
auto it = s.lower_bound(x);
int l = *prev(it) + 1, r = *it - 1;
int id = dc2({l, r});
if (c!=0) mem[id].push_back({x, y, c});
// cout << id << endl;
if (c==0) {
if (x-1>=sub[id].back().first) {
sub[id].back().second = x-1;
sub[id].push_back({x+1, -1});
} else sub[id].back().first = x+1;
}
}
for (int i=0;i<sz;i++) {
if (sub[i].back().first <= ranges[i].r) sub[i].back().second = ranges[i].r;
else sub[i].pop_back();
sub[i].push_back({INF, INF});
}
for (int i=0;i<sz;i++) {
sum[i] = 0;
for (auto [l, r]:sub[i]) {
if (l!=0 && l!=INF) sum[i] += ansR[dc2({l, r})];
}
ansR[i] = sum[i];
// cout << ranges[i].l << " " << ranges[i].r << " " << sum << endl;
for (auto [x, y, c]:mem[i]) {
int id = dc1({x, y, c});
ansS[id] = worth(x, y, i) + c;
ansR[i] = max(ansS[id], ansR[i]);
}
}
cout << SUM - ansR[dc2({1, n})] << endl;
}
