#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
template<typename T>
class SPARSE_TABLE
{
T** table;
function<T(T,T)> func;
int n;
int* log;
int max_b = 0;
public:
SPARSE_TABLE(int MAXN, function<T(T,T)> func) : func(func)
{
log = new int[MAXN+1];
log[0] = -1;
for(int i = 1; i <= MAXN; i++)
{
log[i] = log[i/2]+1;
}
n = 0;
max_b = -1;
}
void setup(int N, T* v)
{
for(int i = 0; i <= max_b; i++)
{
delete[] table[i];
}
delete[] table;
n = N;
int max_lg = log[n];
max_b = max_lg;
table = new T*[max_lg+1];
for(int i = 0; i <= max_lg; i++)
{
table[i] = new T[n];
}
for(int i = 0; i < n; i++)
{
table[0][i] = v[i];
}
for(int bit = 1; bit <= max_lg; bit++)
{
for(int i = 0; i < n; i++)
{
if(i + (1 << bit)-1 < n)
{
table[bit][i] = func(table[bit-1][i],table[bit-1][i + (1 << (bit-1))]);
}
}
}
}
T query(int l, int r)
{
int bit = log[r-l+1];
return func(table[bit][l],table[bit][r-(1 << bit)+1]);
}
};
struct dp
{
set<int> poz;
map<int,ll> ans;
ll dod = 0;
ll down_ans = 0;
ll sum = 0;
void upd()
{
forall(it,poz) ans[it]+=dod;
dod = 0;
}
void merge(dp& d, int level)
{
d.upd();
sum += d.sum;
vi del;
forall(it,poz)
{
if(it <= level)
{
down_ans = min(down_ans,ans[it]+dod);
del.pb(it);
}
}
while(!del.empty())
{
poz.erase(poz.find(del.back()));
del.pop_back();
}
forall(it,d.poz)
{
if(it <= level)
{
d.down_ans = min(d.down_ans,d.ans[it]+d.dod);
del.pb(it);
}
}
while(!del.empty())
{
d.poz.erase(d.poz.find(del.back()));
del.pop_back();
}
// cout << down_ans << " " << d.down_ans << " down_ans\n";
dod += d.down_ans;
forall(it,d.poz)
{
if(poz.find(it) == poz.end())
{
ans[it] = INF_L;
poz.insert(it);
}
ans[it] = min(ans[it],d.ans[it]-dod+down_ans);
auto up = poz.upper_bound(it);
while(up != poz.end() && ans[*up] >= ans[it]+down_ans)
{
poz.erase(up);
up = poz.upper_bound(it);
}
}
down_ans += d.down_ans;
}
void add_star(vector<pair<int,ll>> stars)
{
forall(it,stars)
{
sum += it.ss;
down_ans += it.ss;
}
forall(it,stars)
{
int y = it.ff;
if(poz.find(y) == poz.end())
{
ans[y] = INF_L;
poz.insert(y);
}
ans[y] = min(ans[y],sum-it.ss);
auto up = poz.upper_bound(y);
while(up != poz.end() && ans[*up] >= sum-it.ss)
{
poz.erase(up);
up = poz.upper_bound(y);
}
}
}
};
vector<pair<int,ll>> stars[200001];
int arr[200001];
int pom[200001];
int max_f(int a, int b) {return arr[a] > arr[b] ? a : b;};
SPARSE_TABLE<int> table(200001,max_f);
dp dps[200001];
int f(int l, int r)
{
if(l > r) return -1;
int m = table.query(l,r);
int p1 = f(l,m-1);
int p2 = f(m+1,r);
if(p1 != -1)
{
if(siz(dps[p1].poz) > siz(dps[m].poz)) swap(dps[m],dps[p1]);
dps[m].merge(dps[p1],arr[m]);
}
if(p2 != -1)
{
if(siz(dps[p2].poz) > siz(dps[m].poz)) swap(dps[m],dps[p2]);
dps[m].merge(dps[p2],arr[m]);
}
// cout << m << " tree\n";
// forall(it,dps[m].poz)
// {
// cout << it << " " << dps[m].ans[it] << " dp\n";
// }
// cout << dps[m].sum << " " << dps[m].dod << " " << dps[m].down_ans << " dod\n\n";
return m;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//random_start();
int n;
cin >> n;
rep(i,n) cin >> arr[i+1];
rep2(i,1,n) pom[i] = i;
table.setup(n+1,pom);
int m;
cin >> m;
rep(i,m)
{
int x,y,c;
cin >> x >> y >> c;
stars[x].pb({y,c});
}
rep2(i,1,n)
{
dps[i].add_star(stars[i]);
}
int poz = f(1,n);
dps[poz].upd();
ll ans = dps[poz].down_ans;
forall(it,dps[poz].poz)
{
ans = min(ans,dps[poz].ans[it]);
}
cout << ans << "\n";
}
