#include <cstdio>
#include <vector>
#include <map>
#include <stack>
#include <algorithm>
#define PB push_back
#define X first
#define Y second
using namespace std;
typedef pair < int, int > pii;
typedef vector < int > vi;
typedef long long ll;
const int N = 2e5 + 500;
const int LOG = 18;
map < int, ll > dp[N];
map < int, vi > sjec[N];
int n, m, kol[N];
int A[N], zvj[N], C[N];
int L[N], R[N], pos[N];
int rmq[N][LOG];
int par[N][2];
vector < pii > bitni;
vi T[N][2];
int Q_L[N][2], Q_R[N][2], cur = 0;
ll loga[N][2];
bool cmp(const pii &A,const pii &B){
return A.Y - A.X < B.Y - B.X;
}
void dfs(int x,int fl){
Q_L[x][fl] = cur++;
for(int y : T[x][fl])
dfs(y, fl);
Q_R[x][fl] = cur;
}
void add(int x,int fl, ll y){
for(x += 10; x < N ; x += x & -x)
loga[x][fl] += y;
}
ll get(int x, int fl){
ll ret = 0;
for(x += 10; x ; x -= x & -x)
ret += loga[x][fl];
return ret;
}
inline int maax(int i,int j){
if(A[i] > A[j])
return i;
return j;
}
inline int get_maax(int l,int r){
return maax(rmq[l][kol[r - l + 1]], rmq[r - (1 << kol[r - l + 1]) + 1][kol[r - l + 1]]);
}
ll svi_C = 0;
ll f(int l,int r){
if(r < l) return 0;
if(dp[l][r] != 0) return dp[l][r] - 1;
int mks = get_maax(l, r);
ll ret = f(l, mks - 1) + f(mks + 1, r);
for(int x : sjec[l][r])
ret = max(ret, f(l, pos[x] - 1) + f(pos[x] + 1, r) + C[x]);
dp[l][r] = ret + 1;
return ret;
}
int main(){
scanf("%d", &n);
vector < pii > saz;
for(int i = 1;i <= n;i++){
scanf("%d", A + i);
rmq[i][0] = i;
}
scanf("%d", &m);
for(int i = 1;i <= n;i++)
saz.PB({A[i], i + m});
for(int i = 0;i < m;i++){
scanf("%d%d%d", pos + i, zvj + i, C + i);
saz.PB({zvj[i], i});
}
sort(saz.begin(), saz.end());
for(int i = 0;i < n + m;i++){
if(saz[i].Y < m)
zvj[saz[i].Y] = i + 1;
else
A[saz[i].Y - m] = i + 1;
}
A[0] = n + m + 1, A[n + 1] = n + m + 1;
stack < int > s; s.push(0);
for(int i = 1;i <= n;i++){
for(;A[s.top()] < A[i];s.pop());
par[i][0] = s.top(); s.push(i);
if(par[i][0] < i - 1)
bitni.PB({par[i][0] , i});
T[par[i][0]][0].PB(i);
}
bitni.PB({0, n + 1});
for(;!s.empty();s.pop());
s.push(n + 1);
for(int i = n;i >= 1;i--){
for(;A[s.top()] < A[i];s.pop());
par[i][1] = s.top(); s.push(i);
if(par[i][1] > i + 1)
bitni.PB({i , par[i][1]});
T[par[i][1]][1].PB(i);
}
dfs(0, 0); cur = 0; dfs(n + 1, 1);
for(int i = 1;i <= n + 2;i++){
{for(;(1 << kol[i]) <= i;kol[i]++); kol[i]--;}
rmq[i][0] = i;
}
for(int j = 1;j < LOG;j++){
for(int i = 0;i <= n + 1;i++){
rmq[i][j] = rmq[i][j - 1];
if(i + (1 << (j - 1)) <= n + 1)
rmq[i][j] = maax(rmq[i][j], rmq[i + (1 << (j - 1))][j - 1]);
}
}
for(int i = 0;i < m;i++){
L[i] = pos[i], R[i] = pos[i];
for(int j = LOG - 1;j >= 0;j--){
if(L[i] - (1 << j) >= 1 && A[get_maax(L[i] - (1 << j), pos[i])] < zvj[i])
L[i] -= (1 << j);
if(R[i] + (1 << j) <= n && A[get_maax(pos[i], R[i] + (1 << j))] < zvj[i])
R[i] += (1 << j);
}
L[i]--, R[i]++;
sjec[L[i]][R[i]].PB(i); svi_C += C[i];
}
sort(bitni.begin(), bitni.end(), cmp);
for(pii ja : bitni){
int l = ja.X, r = ja.Y;
int mks = get_maax(l + 1, r - 1);
ll cur = dp[l][mks] + dp[mks][r];
for(int x : sjec[l][r]){
cur = max(cur, (ll)C[x] + get(Q_L[pos[x]][0], 0) + get(Q_L[pos[x]][1], 1) - get(Q_L[l][0], 0) - get(Q_L[r][1], 1));
}
dp[l][r] = cur;
if(A[l] > A[r]){
add(Q_L[r][0], 0, cur);
add(Q_R[r][0], 0, -cur);
}
if(A[l] < A[r]){
add(Q_L[l][1], 1, cur);
add(Q_R[l][1], 1, -cur);
}
}
printf("%lld\n", svi_C - dp[0][n + 1]);
}
