#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<
using namespace std;
// sunt putin penal ca mergea aib
namespace SegmTree {
int n;
vector<int64_t> tree, lazy;
void Init(int n_) {
n = n_;
tree.assign(4 * n, 0);
lazy.assign(4 * n, 0);
}
void Push(int node) {
if (lazy[node] == 0) return;
for (int son : {2 * node + 1, 2 * node + 2}) {
tree[son] += lazy[node];
lazy[son] += lazy[node];
}
lazy[node] = 0;
}
void Add(int node, int left, int right, int x, int y, int64_t val) {
if (x <= left && right <= y) {
tree[node] += val;
lazy[node] += val;
return;
}
Push(node);
int mid = left + (right - left) / 2;
if (x <= mid)
Add(2 * node + 1, left, mid, x, y, val);
if (mid < y)
Add(2 * node + 2, mid + 1, right, x, y, val);
}
int64_t Query(int node, int left, int right, int pos) {
if (left == right) {
return tree[node];
}
Push(node);
int mid = left + (right - left) / 2;
if (pos <= mid)
return Query(2 * node + 1, left, mid, pos);
else
return Query(2 * node + 2, mid + 1, right, pos);
}
void Add(int left, int right, int64_t val) {
Add(0, 0, n - 1, left, right, val);
}
int64_t Query(int pos) {
return Query(0, 0, n - 1, pos);
}
}
namespace DSU {
int n;
vector<int> dad, sz, lft, rgt;
vector<int64_t> dp;
void Init(int n_) {
n = n_;
dad.resize(n), sz.resize(n), lft.resize(n), rgt.resize(n), dp.resize(n);
for (int i = 0; i < n; ++i) {
lft[i] = rgt[i] = i;
dad[i] = -1;
sz[i] = 1;
dp[i] = 0;
}
}
int Find(int x) {
if (dad[x] == -1) return x;
return dad[x] = Find(dad[x]);
}
void Union(int x, int y) {
x = Find(x), y = Find(y);
if (x == y) return;
if (sz[x] < sz[y]) swap(x, y);
// dbg() "Union: " << name(x) name(y) endl;
sz[x] += sz[y];
dad[y] = x;
SegmTree::Add(lft[x], rgt[x], dp[y]);
SegmTree::Add(lft[y], rgt[y], dp[x]);
dp[x] += dp[y];
lft[x] = min(lft[x], lft[y]);
rgt[x] = max(rgt[x], rgt[y]);
}
void Update(int x, int64_t val) {
// dbg() "DSU Upd: " << name(x) name(val) endl;
x = Find(x);
dp[x] = max(dp[x], val);
}
int64_t Get(int node) {
return dp[Find(node)];
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
vector<int> h(n);
vector<vector<int>> walls(n + 1);
for (int i = 0; i < n; ++i) {
cin >> h[i];
walls[h[i]].emplace_back(i);
}
int m; cin >> m;
vector<vector<pair<int, int>>> stars(n + 1);
int64_t ans = 0;
for (int i = 0; i < m; ++i) {
int x, y, c; cin >> x >> y >> c; --x, --y;
stars[y].emplace_back(x, c);
ans += c;
}
// le sterg pe toate si incerc sa pastrez o suma cat mai mare
DSU::Init(n);
SegmTree::Init(n);
for (int y = 0; y <= n; ++y) {
for (int &x : walls[y]) {
if (x - 1 >= 0 && h[x - 1] <= y) {
DSU::Union(x - 1, x);
}
if (x + 1 < n && h[x + 1] <= y) {
DSU::Union(x, x + 1);
}
}
// for (int i = 0; i < n; ++i) {
// dbg() name(i) name(DSU::Get(i)) endl;
// }
for (auto &star : stars[y]) {
int x, c; tie(x, c) = star;
DSU::Update(x, c + SegmTree::Query(x));
}
}
for (int i = 1; i < n; ++i) {
DSU::Union(i - 1, i);
}
cout << ans - DSU::Get(0) << endl;
}
