#pragma GCC target ("avx")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include"bits/stdc++.h"
#include<unordered_set>
#include<unordered_map>
#include<random>
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };
struct RMaxQ{
private:
int N;
vector<long long> node, lazy;
long long DEFAULT;
public:
void init(int n, long long def=-9223372036854775807LL){
DEFAULT = def;
N = 1;
while(N < n) N = (N<<1);
node.assign(2*N-1, DEFAULT);
lazy.assign(2*N-1, 0);
}
void eval(int k, int l, int r){
node[k] += lazy[k];
if(r-l > 1){
lazy[(k<<1)+1] += lazy[k];
lazy[(k<<1)+2] += lazy[k];
}
lazy[k] = 0LL;
}
void add(int a, long long x){
add(a, a+1, x);
}
void add(int a, int b, long long x, int k=0, int l=0, int r=-1){
if(a >= b) return;
if(r == -1) r = N;
eval(k, l, r);
if(b <= l || r <= a) return;
if(a <= l && r <= b){
lazy[k] += x;
eval(k, l, r);
}
else{
add(a, b, x, (k<<1)+1, l, (l+r)>>1);
add(a, b, x, (k<<1)+2, (l+r)>>1, r);
node[k] = std::max(node[(k<<1)+1], node[(k<<1)+2]);
}
}
long long max(int a, int b, int k=0, int l=0, int r=-1){
if(a >= b) return -9223372036854775807LL;
if(r == -1) r = N;
if(b <= l || r <= a) return -9223372036854775807LL;
eval(k, l, r);
if(a <= l && r <= b) return node[k];
return std::max(max(a, b, (k<<1)+1, l, (l+r)>>1), max(a, b, (k<<1)+2, (l+r)>>1, r));
}
long long m;
int find(int a, int b, int k=0, int l=0, int r=-1){
if(r == -1){
m = max(a, b);
r = N;
}
if(r <= a || b <= l) return INT_MAX;
if(r-l == 1){
if(node[k] == m) return l;
else return INT_MAX;
}
if(a <= l && r <= b){
int valueL = max(a, b, (k<<1)+1, l, (l+r)/2);
int valueR = max(a, b, (k<<1)+2, (l+r)/2, r);
if(valueL == m) return find(a, b, (k<<1)+1, l, (l+r)>>1);
if(valueR == m) return find(a, b, (k<<1)+2, (l+r)>>1, r);
return INT_MAX;
}
return std::min(find(a, b, (k<<1)+1, l, (l+r)>>1), find(a, b, (k<<1)+2, (l+r)>>1, r));
}
long long operator [](int a){
return max(a, a+1);
}
};
struct RMinQ{
private:
int N;
vector<long long> node, lazy;
vector<bool> lazyFlg;
long long DEFAULT;
public:
void init(int n, long long def=9223372036854775807LL){
DEFAULT = def;
N = 1;
while(N < n) N = (N<<1);
node.assign(2*N-1, DEFAULT);
lazy.assign(2*N-1, 0);
lazyFlg.assign(2*N-1, false);
}
void eval(int k, int l, int r){
if(lazyFlg[k]){
node[k] = lazy[k];
if(r-l > 1){
lazy[(k<<1)+1] = lazy[k];
lazyFlg[(k<<1)+1] = true;
lazy[(k<<1)+2] = lazy[k];
lazyFlg[(k<<1)+2] = true;
}
lazy[k] = 0LL;
lazyFlg[k] = false;
}
}
void update(int a, long long x){
update(a, a+1, x);
}
void update(int a, int b, long long x, int k=0, int l=0, int r=-1){
if(a >= b) return;
if(r == -1) r = N;
eval(k, l, r);
if(b <= l || r <= a) return;
if(a <= l && r <= b){
lazy[k] = x;
lazyFlg[k] = true;
eval(k, l, r);
}
else{
update(a, b, x, (k<<1)+1, l, (l+r)>>1);
update(a, b, x, (k<<1)+2, (l+r)>>1, r);
node[k] = std::min(node[(k<<1)+1], node[(k<<1)+2]);
}
}
long long min(int a, int b, int k=0, int l=0, int r=-1){
if(a >= b) return 9223372036854775807LL;
if(r == -1) r = N;
if(b <= l || r <= a) return 9223372036854775807LL;
eval(k, l, r);
if(a <= l && r <= b) return node[k];
return std::min(min(a, b, (k<<1)+1, l, (l+r)>>1), min(a, b, (k<<1)+2, (l+r)>>1, r));
}
long long m;
int find(int a, int b, int k=0, int l=0, int r=-1){
if(r == -1){
m = min(a, b);
r = N;
}
if(r <= a || b <= l) return INT_MAX;
if(r-l == 1){
if(node[k] == m) return l;
else return INT_MAX;
}
if(a <= l && r <= b){
int valueL = min(a, b, (k<<1)+1, l, (l+r)/2);
int valueR = min(a, b, (k<<1)+2, (l+r)/2, r);
if(valueL == m) return find(a, b, (k<<1)+1, l, (l+r)>>1);
if(valueR == m) return find(a, b, (k<<1)+2, (l+r)>>1, r);
return INT_MAX;
}
return std::min(find(a, b, (k<<1)+1, l, (l+r)>>1), find(a, b, (k<<1)+2, (l+r)>>1, r));
}
};
int N;
RMaxQ A;
int M;
int X[200000], Y[200000], C[200000];
ll sumC = 0;
vector<pair<int,int>> s[200000]; // stars for each x
RMinQ rmq; int c[200000] ={};
int bottomNode[200000]; // bottom node for each x
int cnt = 0;
ll dp[200000];
RMaxQ depth;
ll dpChi[200000];
int dfs(int l, int r, int u){
if(l > r) return -1;
int n = cnt; cnt++;
int m = A.find(l, r+1);
int d = A[m]+1;
bottomNode[m] = n;
int chi0 = dfs(l, m-1, d-1);
int chi1 = dfs(m+1, r, d-1);
if(chi0 != -1 && chi1 != -1){
depth.add(chi0, chi1, dp[chi1]);
depth.add(chi1, cnt, dp[chi0]);
}
dp[n] = (chi0 != -1 ? dp[chi0] : 0) + (chi1 != -1 ? dp[chi1] : 0);
dpChi[n] = dp[n];
while(rmq.min(l, r+1) <= u){
int i = rmq.find(l, r+1);
int b = bottomNode[i];
dp[n] = max(dp[n], s[i][c[i]].second + depth.max(b, b+1) + dpChi[b]);
c[i]++;
if(c[i] < s[i].size()) rmq.update(i, s[i][c[i]].first);
else rmq.update(i, N+1);
}
return n;
}
signed main(){
scanf("%d", &N);
A.init(N, 0);
rep(i, N){
int a;
scanf("%d", &a);
A.add(i, a);
}
scanf("%d", &M);
rep(i, M){
scanf("%d%d%d", X+i, Y+i, C+i);
X[i]--;
s[X[i]].pb({ Y[i], C[i] });
sumC += C[i];
}
rmq.init(N, N+1);
rep(i, N){
if(s[i].size() == 0) continue;
sort(all(s[i]));
rmq.update(i, s[i][0].first);
}
depth.init(N, 0);
dfs(0, N-1, N);
printf("%lld\n", sumC-dp[0]);
}
