#include <bits/stdc++.h>
using namespace std;
#define int long long
struct SegmentTree{
vector<pair<int, int>> st;
int n;
void init(vector<int> a){
n = a.size() - 1;
st.assign(n * 2 + 2, {0, 0});
for(int i = 1; i <= n; i++) st[i + n] = {a[i], i};
for(int i = n; i >= 1; i--) st[i] = max(st[i * 2], st[i * 2 + 1]);
}
pair<int, int> get(int l, int r){
l += n; r += n + 1;
pair<int, int> ans = {0, 0};
while(l < r){
if(l & 1) ans = max(ans, st[l++]);
if(r & 1) ans = max(ans, st[--r]);
l >>= 1; r >>= 1;
}
return ans;
}
} st;
struct SexSet{
set<pair<int, int>> S; //lưu độ cao, giá trị
int offset;
SexSet(){
offset = 0;
S.insert(make_pair(0, 0));
}
void add_element(pair<int, int> x){
x.second -= offset;
auto it = S.lower_bound({x.first, 1e18});
if(it != S.begin() && (*prev(it)).second >= x.second) return;
while(true){
auto it = S.lower_bound({x.first, -1e18});
if(it == S.end() || (*it).second > x.second) break;
S.erase(it); //xóa nhx thg cao hơn/bằng mà có giá trị tệ hơn
}
S.insert(x);
}
pair<int, int> front(){
pair<int, int> ans = *S.begin();
ans.second += offset;
return ans;
}
};
void gate_keep(SexSet &a, int bound){
int mx = 0;
while(a.S.size()){
pair<int, int> f = a.front();
if (f.first > bound) break;
a.S.erase(a.S.begin());
mx = f.second;
}
a.add_element({bound, mx});
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n; cin >> n;
vector<int> a(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
int m; cin >> m;
vector<vector<pair<int, int>>> star(n + 1);
int ans = 0;
for(int i = 1; i <= m; i++){
int x, y, z; cin >> x >> y >> z;
star[x].push_back({y, z});
ans += z;
}
function<SexSet(int, int)> dnc = [&](int l, int r) -> SexSet {
if(l > r) return SexSet();
int mid = st.get(l, r).second;
SexSet ll = dnc(mid + 1, r);
SexSet rr = dnc(l, mid - 1);
gate_keep(ll, a[mid]);
gate_keep(rr, a[mid]);
int s1 = ll.front().second, s3 = rr.front().second;
rr.offset += s1;
ll.offset += s3;
if(ll.S.size() > rr.S.size()){
for(auto [u, v]: star[mid]) ll.add_element({u, v + s1 + s3});
for(auto [u, v]: rr.S) ll.add_element({u, v + rr.offset});
return ll;
}else{
for(auto [u, v]: star[mid]) rr.add_element({u, v + s1 + s3});
for(auto [u, v]: ll.S) rr.add_element({u, v + ll.offset});
return rr;
}
};
st.init(a);
SexSet suc = dnc(1, n);
cout << ans - (*(suc.S).rbegin()).second - suc.offset << "\n";
}
