#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>
#include <stack>
typedef long long llong;
const int MAXLOG = 19;
const int MAXN = 400000 + 10;
const int INF = 1e9;
int n, m;
int a[MAXN];
int h[MAXN];
int cntSegm;
struct Sparse
{
int sparse[MAXLOG][MAXN];
void build(int par[])
{
for (int i = 1 ; i <= cntSegm ; ++i)
{
sparse[0][i] = par[i];
}
for (int log = 1 ; (1 << log) <= cntSegm ; ++log)
{
for (int i = 1 ; i <= cntSegm ; ++i)
{
sparse[log][i] = sparse[log - 1][sparse[log - 1][i]];
}
}
}
int find(int x, int y)
{
for (int log = MAXLOG - 1 ; log >= 0 ; --log)
{
if (h[sparse[log][x]] < y)
{
x = sparse[log][x];
}
}
return x;
}
};
struct SegmentTree
{
struct Node
{
llong value;
llong lazy;
Node()
{
value = lazy = 0;
}
};
Node tree[4*MAXN];
void push(int node, int l, int r)
{
if (l == r)
{
tree[node].value += tree[node].lazy;
} else
{
tree[2*node].lazy += tree[node].lazy;
tree[2*node + 1].lazy += tree[node].lazy;
}
tree[node].lazy = 0;
}
void update(int l, int r, int node, int queryL, int queryR, llong queryValue)
{
push(node, l, r);
if (queryR < l || r < queryL)
{
return;
}
if (queryL <= l && r <= queryR)
{
tree[node].lazy += queryValue;
push(node, l, r);
return;
}
int mid = (l + r) / 2;
update(l, mid, 2*node, queryL, queryR, queryValue);
update(mid + 1, r, 2*node + 1, queryL, queryR, queryValue);
}
llong query(int l, int r, int node, int queryPos)
{
push(node, l, r);
if (l == r)
{
return tree[node].value;
}
int mid = (l + r) / 2;
if (queryPos <= mid) return query(l, mid, 2*node, queryPos);
return query(mid + 1, r, 2*node + 1, queryPos);
}
void update(int l, int r, llong val)
{
assert(l >= 0 && r <= cntSegm);
update(0, cntSegm, 1, l, r, val);
}
llong query(int pos)
{
return query(0, cntSegm, 1, pos);
}
};
int x[MAXN];
int y[MAXN];
int c[MAXN];
int in[MAXN];
int out[MAXN];
int par[MAXN];
llong dp[MAXN];
llong sum[MAXN];
int leftSegm[MAXN];
int rightSegm[MAXN];
int leftBigger[MAXN];
std::vector <int> g[MAXN];
std::vector <int> stars[MAXN];
std::stack <int> st;
SegmentTree tree;
Sparse sparse;
int timer;
void buildDFS(int node)
{
in[node] = timer++;
for (const int &u : g[node])
{
buildDFS(u);
}
out[node] = timer - 1;
}
void solveDFS(int node)
{
for (const int &u : g[node])
{
solveDFS(u);
sum[node] += dp[u];
}
llong res = sum[node];
tree.update(in[node], out[node], sum[node]);
for (const int &idx : stars[node])
{
res = std::max(res, c[idx] + tree.query(in[par[leftSegm[x[idx]]]]));
}
dp[node] = res;
tree.update(in[node], out[node], -dp[node]);
}
void solve()
{
a[0] = INF;
h[0] = INF;
st.push(0);
for (int i = 1 ; i <= n ; ++i)
{
while (a[st.top()] < a[i])
{
st.pop();
}
leftBigger[i] = st.top();
st.push(i);
}
while (st.size())
{
st.pop();
}
for (int i = 1 ; i <= n ; ++i)
{
bool wasThere = false;
if (a[leftBigger[i]] == a[i])
{
wasThere = true;
leftSegm[i] = rightSegm[leftBigger[i]];
} else
{
leftSegm[i] = ++cntSegm;
}
rightSegm[i] = ++cntSegm;
h[leftSegm[i]] = a[i];
h[rightSegm[i]] = a[i];
while (st.size() && a[st.top()] < a[i])
{
if (!wasThere && (par[leftSegm[st.top()]] == 0 || h[par[leftSegm[st.top()]]] > a[i]))
{
par[rightSegm[st.top()]] = leftSegm[i];
par[leftSegm[st.top()]] = leftSegm[i];
}
st.pop();
}
if (st.size())
{
if (a[st.top()] > a[i])
{
par[leftSegm[i]] = rightSegm[st.top()];
par[rightSegm[i]] = rightSegm[st.top()];
} else
{
par[leftSegm[i]] = par[rightSegm[st.top()]];
par[rightSegm[i]] = par[rightSegm[st.top()]];
}
}
st.push(i);
}
for (int i = 1 ; i <= cntSegm ; ++i)
{
g[par[i]].push_back(i);
}
sparse.build(par);
llong sumStars = 0;
for (int i = 1 ; i <= m ; ++i)
{
stars[par[sparse.find(leftSegm[x[i]], y[i])]].push_back(i);
sumStars += c[i];
}
buildDFS(0);
solveDFS(0);
std::cout << sumStars - dp[0] << '\n';
}
void input()
{
std::cin >> n;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> a[i];
}
std::cin >> m;
for (int i = 1 ; i <= m ; ++i)
{
std::cin >> x[i] >> y[i] >> c[i];
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
