#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int>pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
const int N=2e5+5;
int n, m, sz, a[N], cl[N], cr[N], x[N], y[N], c[N], mx[4*N], la[4*N], p[N], td[N];
ll dp[N], pd[N], mm[N], ans[4*N], fuck;
vector<pii>u[N];
int max(int x, int lx, int rx, int l, int r){
if(lx>=r || rx<=l)
return n;
if(lx>=l && rx<=r)
return mx[x];
int mid=(lx+rx)/2;
int l1=max(2*x+1, lx, mid, l, r);
int r1=max(2*x+2, mid, rx, l, r);
if(a[l1]<=a[r1])
return r1;
return l1;
}
void max(int x, int lx, int rx, int l, int r, ll v){
if(rx<=l || lx>=r)
return;
if(lx>=l && rx<=r){
ans[x]=max(ans[x], v);
return;
}
int mid=(lx+rx)/2;
if(la[x]){
ans[2*x+1]=ans[2*x+2]=0;
la[2*x+1]=la[2*x+2]=1;
la[x]=0;
}
ans[2*x+1]=max(ans[x], ans[2*x+1]);
ans[2*x+2]=max(ans[x], ans[2*x+2]);
max(2*x+1, lx, mid, l, r, v);
max(2*x+2, mid, rx, l, r, v);
}
ll num(int x, int l, int r, int y){
if(r-l==1)
return ans[x]+fuck;
if(la[x]){
la[2*x+1]=la[2*x+2]=1;
ans[2*x+1]=ans[2*x+2]=0;
la[x]=0;
}
ans[2*x+1]=max(ans[2*x+1], ans[x]);
ans[2*x+2]=max(ans[2*x+2], ans[x]);
int mid=(l+r)/2;
if(y<mid)
return num(2*x+1, l, mid, y);
return num(2*x+2, mid, r, y);
}
void dsu(int l1, int r1, int l2, int r2){
int w1=p[l1];
int w2=p[l2];
if(u[w1].size()>u[w2].size()){
swap(w1, w2);
swap(l1, l2);
swap(r1, r2);
}
for(pii ww: u[w1]){
dp[ww.S]+=pd[w1]-pd[w2];
u[w2].push_back(ww);
mm[w2]=max(mm[w2], dp[ww.S]+pd[w2]);
}
for(int i=l1;i<r1;++i)
p[i]=w2;
}
ll sol(int l, int r){
if(l==r)
return 0;
int id=max(0, 0, sz, l, r);
int s1=td[l]-td[id], s2=td[id+1]-td[r];
ll lr=0, zz=0, rl=0;
if(s1<s2){
ll z=sol(l, id);
if(a[id]<n-1)
lr=num(0, 0, sz, a[id]+1);
else
lr=z;
la[0]=1;
ans[0]=0;
fuck=0;
zz=sol(id+1, r);
if(a[id]<n-1)
rl=num(0, 0, sz, a[id]+1);
else
rl=zz;
if(id>l){
pd[p[l]]+=rl;
mm[p[l]]+=rl;
fuck+=lr;
int v=p[l];
for(pii w: u[v])
max(0, 0, sz, w.F+1, n, dp[w.S]+pd[v]-fuck);
}
if(id+1<r){
pd[p[id+1]]+=lr;
mm[p[id+1]]+=lr;
}
}
else{
ll z=sol(id+1, r);
if(a[id]<n-1)
lr=num(0, 0, sz, a[id]+1);
else
lr=z;
la[0]=1;
ans[0]=0;
fuck=0;
zz=sol(l, id);
if(a[id]<n-1)
rl=num(0, 0, sz, a[id]+1);
else
rl=zz;
if(id+1<r){
pd[p[id+1]]+=rl;
mm[p[id+1]]+=rl;
fuck+=lr;
int v=p[id+1];
for(pii w: u[v])
max(0, 0, sz, w.F+1, n, dp[w.S]+pd[v]-fuck);
}
if(id>l){
pd[p[l]]+=lr;
mm[p[l]]+=lr;
}
}
for(pii w: u[id]){
dp[w.S]=c[w.S]+lr+rl;
mm[id]=max(mm[id], dp[w.S]);
max(0, 0, sz, w.F+1, n, dp[w.S]-fuck);
}
if(id+1<r)
dsu(id, id+1, id+1, r);
if(id>l)
dsu(l, id, id, r);
return max(rl+lr, mm[p[l]]);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n;
for(int i=0;i<n;++i){
cin>>a[i];
--a[i];
}
a[n]=-1;
cin>>m;
for(int i=0;i<m;++i){
cin>>x[i]>>y[i]>>c[i];
u[--x[i]].push_back({--y[i], i});
}
for(int i=n-1;i>=0;--i){
sort(all(u[i]));
td[i]=td[i+1]+u[i].size();
}
sz=1;
while(sz<n)
sz*=2;
iota(mx+sz-1, mx+n+sz-1, 0);
for(int i=sz-2;i>=0;--i){
if(a[mx[2*i+1]]<a[mx[2*i+2]])
mx[i]=mx[2*i+2];
else
mx[i]=mx[2*i+1];
}
iota(p, p+n, 0);
ll z=0;
for(int i=0;i<m;++i)
z+=c[i];
z-=sol(0, n);
cout<<z<<'\n';
}
