#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
vector<ll> a(N);
vector<pair<ll,int>> sorted;
for(int i=0;i<N;i++){
cin >> a[i];
sorted.push_back({a[i],i});
}
sort(sorted.begin(),sorted.end());
int M;
cin >> M;
vector<priority_queue<vector<ll>,vector<vector<ll>>,greater<>>> star(N+1);
ll tot =0;
for(int i=0;i<M;i++){
ll x,y,c;
cin >> x >> y >> c;
tot+=c;
x--;
star[x].push({y,c});
}
ll ans=0;
vector<ll> offset(N+1,0),parent(N+1,0),taille(N+1,0),score(N+1,0);
for(int i=0;i<N;i++)
parent[i]=i;
for(int i=0;i<N;i++){
int x = sorted[i].second;
int left=N,right=N;
int leftmost=x-1,rightmost=x+1;
if(x-1>=0&&taille[x-1]!=0){
left=parent[x-1];
leftmost-=taille[x-1];
if(star[left].size()>star[x].size()){
swap(star[left],star[x]);
swap(offset[left],offset[x]);
}
while(!star[left].empty()){
vector<ll> cur=star[left].top();
star[left].pop();
cur[1]+=offset[x]-offset[left];
star[x].push(cur);
}
}
if(x+1<N&&taille[x+1]!=0){
right=parent[x+1];
rightmost+=taille[x+1];
if(star[right].size()>star[x].size()){
swap(star[right],star[x]);
swap(offset[right],offset[x]);
}
while(!star[right].empty()){
vector<ll> cur=star[right].top();
star[right].pop();
cur[1]+=offset[x]-offset[right];
star[x].push(cur);
}
}
taille[leftmost+1]=rightmost-leftmost-1;
taille[rightmost-1]=rightmost-leftmost-1;
parent[rightmost-1]=parent[leftmost+1]=x;
ll limit = 1e9;
if(leftmost>=0)
limit=min(limit,a[leftmost]);
if(rightmost<N)
limit=min(limit,a[rightmost]);
ll best=0;
while(!star[x].empty()&&star[x].top()[0]<=limit){
best=max(best,star[x].top()[1]-offset[x]);
star[x].pop();
}
offset[x]+=best;
score[x]=score[left]+score[right]+best;
ans=max(ans,score[x]);
}
cout << tot-ans << endl;
}
