/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 2e5 + 10;
struct point
{
int x, y;
ll c;
};
bool cmp(point p1, point p2)
{
return p1.y < p2.y;
}
point star[maxn];
int n, m, a[maxn];
vector < pair < int, ll > > loc_star[maxn];
void input()
{
cin >> n;
for (int i = 1; i <= n; i ++)
cin >> a[i];
cin >> m;
for (int i = 1; i <= m; i ++)
{
cin >> star[i].x >> star[i].y >> star[i].c;
loc_star[star[i].x].push_back({star[i].y, star[i].c});
}
///sort(star + 1, star + m + 1, cmp);
}
int lc[maxn], rc[maxn], par[maxn];
int cartesian_tree()
{
for (int i = 1; i <= n; i ++)
{
lc[i] = rc[i] = -1;
par[i] = 0;
}
stack < int > st;
int root = -1;
for (int i = 1; i <= n; i ++)
{
while(!st.empty() && a[st.top()] < a[i])
{
lc[i] = st.top();
st.pop();
}
if (st.empty())
root = i;
else
{
par[i] = st.top();
rc[st.top()] = i;
}
if (lc[i] != -1)
par[lc[i]] = i;
st.push(i);
}
return root;
/**cout << "cartesian" << endl;
for (int i = 1; i <= n; i ++)
cout << i << " " << lc[i] << " " << rc[i] << endl;*/
}
const int maxlog = 21;
int tin[maxn], tout[maxn], timer;
int jump[maxlog][maxn];
vector < pair < int, ll > > links[maxn];
void create_links(int v)
{
jump[0][v] = par[v];
for (int j = 1; j < maxlog; j ++)
jump[j][v] = jump[j - 1][jump[j - 1][v]];
for (pair < int, ll > cur : loc_star[v])
{
int to = v;
for (int bit = maxlog - 1; bit >= 0; bit --)
{
if (jump[bit][to] == 0)
continue;
if (a[jump[bit][to]] < cur.first)
to = jump[bit][to];
}
links[to].push_back({v, cur.second});
}
tin[v] = ++ timer;
if (lc[v] != -1)
create_links(lc[v]);
if (rc[v] != -1)
create_links(rc[v]);
tout[v] = timer;
}
struct bit
{
ll fen[maxn];
void update(int v, ll val)
{
for (int i = v; i < maxn; i += (i & -i))
fen[i] += val;
}
ll query(int v)
{
ll sum = 0;
for (int i = v; i > 0; i -= (i & -i))
sum += fen[i];
return sum;
}
void range_update(int l, int r, ll val)
{
update(l, val);
update(r + 1, - val);
}
};
bit tree_above, tree_under;
ll dp[maxn];
void dfs(int v)
{
ll sum_dp = 0;
if (lc[v] != -1)
{
dfs(lc[v]);
sum_dp += dp[lc[v]];
}
if (rc[v] != -1)
{
dfs(rc[v]);
sum_dp += dp[rc[v]];
}
dp[v] = sum_dp;
tree_under.range_update(tin[v], tout[v], sum_dp);
for (pair < int, ll > cur : links[v])
{
//cout << v << " : " << cur.first << " : " << cur.second << endl;
dp[v] = max(dp[v], cur.second + tree_under.query(tin[cur.first]) - tree_above.query(tin[cur.first]));
}
//cout << "vertex " << v << " " << dp[v] << endl;
tree_above.range_update(tin[v], tout[v], dp[v]);
}
void solve()
{
input();
int root = cartesian_tree();
create_links(root);
dfs(root);
/// remember to subtract
ll ans = 0;
for (int i = 1; i <= m; i ++)
ans += star[i].c;
ans -= dp[root];
cout << ans << endl;
}
int main()
{
speed();
solve();
return 0;
}
