#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long
using i64 = long long;
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
struct Sp{
vector <vector<int>> T;
int _s;
Sp(auto &a, int s){
_s = s;
T.resize(20);
int n = a.size();
for ( auto &x: T ){
x.resize(n);
}
T[0] = a;
for ( auto &u: T[0] ) u *= _s;
for ( int i = 1; i < 20; i++ ){
int k = 1 << i - 1;
for ( int j = 0; j < n; j++ ){
T[i][j] = min(T[i - 1][j], T[i - 1][min(n - 1, j + k)]);
}
}
}
int get(int l, int r){
int lg = __lg(r - l + 1), k = 1 << lg;
return min(T[lg][l], T[lg][r - k + 1]) * _s;
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vector <int> a(n);
for ( auto &u: a ) cin >> u;
int m; cin >> m;
vector <int> X(m), Y(m), C(m);
vector <vector<int>> G(n);
for ( int i = 0; i < m; i++ ){
cin >> X[i] >> Y[i] >> C[i];
--X[i];
G[X[i]].pb(i);
}
vector <int> L(m), R(m);
Sp sp(a, -1);
for ( int i = 0; i < n; i++ ){
for ( auto &j: G[i] ){
int l = 0, r = n;
L[j] = R[j] = i;
while ( l < L[j] ){
int md = (l + L[j]) / 2;
if ( sp.get(md, L[j]) >= Y[j] ){
l = md + 1;
} else L[j] = md;
}
while ( R[j] + 1 < r ){
int md = (R[j] + r) / 2;
if ( sp.get(R[j], md) >= Y[j] ){
r = md;
} else R[j] = md;
}
R[j]++, L[j]++, X[j]++;
}
}
vector <int> pos(m);
iota(all(pos), 0);
sort(all(pos), [&](int &u, int &v){
return Y[u] < Y[v];
});
vector <vector<int>> dp(n + 2, vector <int> (n + 1)), t(n + 1);
for ( int i = 0; i < m; i++ ){
t[X[i]].pb(i);
}
for ( int l = n; l > 0; l-- ){
for ( int r = l; r <= n; r++ ){
chmax(dp[l][r], max(dp[l + 1][r], dp[l][r - 1]));
for ( int k = l; k <= r; k++ ){
for ( auto &i: t[k] ){
if ( L[i] < l || R[i] > r ){
continue;
}
chmax(dp[l][r], dp[l][k - 1] + dp[k + 1][r] + C[i]);
}
}
}
}
cout << accumulate(all(C), 0LL) - dp[1][n];
cout << '\n';
}
