#include <bits/stdc++.h>
#define N 200005
#define ls(u) tr[u].ls
#define rs(u) tr[u].rs
using namespace std;
typedef long long ll;

int n, a[N], m, stk[N], tp;
ll ans;

struct Pnt
{
    int h, c;
};
vector <Pnt> vec[N];

struct Seg { int ls, rs; ll mx, tg; } tr[N<<5];
int rt[N], tot;

int lson[N], rson[N];

void pushdown (int u)
{
    ll tg=tr[u].tg; tr[u].tg=0;
    if (ls(u)) { tr[ls(u)].mx+=tg; tr[ls(u)].tg+=tg; }
    if (rs(u)) { tr[rs(u)].mx+=tg; tr[rs(u)].tg+=tg; }
}
void upd (int &u, int l, int r, int id, ll num)
{
    if (!u) { u=++tot; }
    if (l==r) { tr[u].mx=max(tr[u].mx, num); return; }
    int md=(l+r)>>1;
    pushdown(u);
    if (id<=md) { upd(ls(u), l, md, id, num); }
    else { upd(rs(u), md+1, r, id, num); }
    tr[u].mx=max(tr[ls(u)].mx, tr[rs(u)].mx);
}
ll qry (int u, int l, int r, int ql, int qr)
{
    if (!u) { return 0; }
    if (ql>r || qr<l) { return 0; }
    if (ql<l && r<=qr) { return tr[u].mx; }
    pushdown(u);
    int md=(l+r)>>1;
    return max(qry(ls(u), l, md, ql, qr), qry(rs(u), md+1, r, ql, qr));
}
void add (int u, int l, int r, int ql, int qr, ll tg)
{
    if (!u) { return; }
    if (ql>r || qr<l) { return; }
    if (ql<=l && r<=qr) { tr[u].mx+=tg; tr[u].tg+=tg; return; }
    pushdown(u);
    int md=(l+r)>>1;
    add(ls(u), l, md, ql, qr, tg);
    add(rs(u), md+1, r, ql, qr, tg);
    tr[u].mx=max(tr[ls(u)].mx, tr[rs(u)].mx);
}
void merge (int &u, int v1, int v2, int l, int r)
{
    if (!v1) { u=v2; return; }
    if (!v2) { u=v1; return; }
    u=v1;
    pushdown(v1); pushdown(v2);
    if (l==r) { tr[u].mx=max(tr[v1].mx, tr[v2].mx); return; }
    int md=(l+r)>>1;
    merge(ls(u), ls(v1), ls(v2), l, md);
    merge(rs(u), rs(v1), rs(v2), md+1, r);
    tr[u].mx=max(tr[ls(u)].mx, tr[rs(u)].mx);
}

void dfs (int u)
{
    if (!u) { return; }
    dfs(lson[u]); dfs(rson[u]);

    ll num1=qry(rt[rson[u]], 1, n, 1, a[u]);
    ll num2=qry(rt[lson[u]], 1, n, 1, a[u]);

    add(rt[lson[u]], 1, n, 1, n, num1);
    add(rt[rson[u]], 1, n, 1, n, num2);

    merge(rt[u], rt[lson[u]], rt[rson[u]], 1, n, a[u]);

    for (int i=0; i<(int)vec[u].size(); i++) {
        int h=vec[u][i].h, c=vec[u][i].c;
        upd(rt[u], 1, n, h, c+num1+num2);
    }
}

int main ()
{
    // freopen("0test.in", "r", stdin);
    // freopen("0test.out", "w", stdout);

    scanf("%d", &n);
    for (int i=1; i<=n; i++) { scanf("%d", &a[i]); }
    scanf("%d", &m);
    for (int i=1; i<=m; i++) {
        int x, y, c; scanf("%d %d %d", &x, &y, &c);
        vec[x].push_back((Pnt){ y, c });
        ans+=c;
    }

    for (int i=1; i<=n; i++) {
        stk[tp+1]=0;
        while (tp && a[stk[tp]]<=a[i]) { tp--; }
        if (tp) { rson[stk[tp]]=i; }
        lson[i]=stk[tp+1];
        stk[++tp]=i;
    }
    dfs(stk[1]);
    
    // for (int i=1; i<=n; i++) { cout<<i<<" "<<lson[i]<<" "<<rson[i]<<endl; }

    ans-=tr[rt[stk[1]]].mx;
    printf("%lld\n", ans);

    return 0;
}

In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from answer.code:1:
/usr/include/c++/13/bits/stl_algo.h: In instantiation of ‘_OutputIterator std::__merge(_InputIterator1, _InputIterator1, _InputIterator2, _InputIterator2, _OutputIterator, _Compare) [with _InputIterator1 = int; _InputIterator2 = int; _OutputIterator = int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<int>]’:
/usr/include/c++/13/bits/stl_algo.h:5016:37:   required from ‘_OIter std::merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare) [with _IIter1 = int; _IIter2 = int; _OIter = int; _Compare = int]’
answer.code:82:10:   required from here
/usr/include/c++/13/bits/stl_algo.h:4909:15: error: invalid type argument of unary ‘*’ (have ‘int’)
 4909 |               *__result = *__first2;
      |               ^~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:4909:27: error: invalid type argument of unary ‘*’ (have ‘int’)
 4909 |               *__result = *__first2;
      |                           ^~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:4914:15: error: invalid type argument of unary ‘*’ (have ‘int’)
 4914 |               *__result = *__first1;
      |               ^~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:4914:27: error: invalid type argument of unary ‘*’ (have ‘int’)
 4914 |               *__result = *__first1;
      |                           ^~~~~~~~~
In file included from /usr/include/c++/13/bits/stl_algobase.h:71,
                 from /usr/include/c++/13/algorithm:60:
/usr/include/c++/13/bits/predefined_ops.h: In instantiation of ‘constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = int; _Iterator2 = int; _Compare = int]’:
/usr/include/c++/13/bits/stl_algo.h:4907:14:   required from ‘_OutputIterator std::__merge(_InputIterator1, _InputIterator1, _InputIterator2, _InputIterator2, _OutputIterator, _Compare) [with _InputIterator1 = int; _InputIterator2 = int; _OutputIterator = int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<int>]’
/usr/include/c++/13/bits/stl_algo.h:5016:37:   required from ‘_OIter std::merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare) [with _IIter1 = int; _IIter2 = int; _OIter = int; _Compare = int]’
answer.code:82:10:   required from here
/usr/include/c++/13/bits/predefined_ops.h:158:31: error: invalid type argument of unary ‘*’ (have ‘int’)
  158 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                               ^~~~~~
/usr/include/c++/13/bits/predefined_ops.h:158:39: error: invalid type argument of unary ‘*’ (have ‘int’)
  158 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                                       ^~~~~~
/usr/include/c++/13/bits/predefined_ops.h:158:30: error: expression cannot be used as a function
  158 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~
answer.code: In function ‘int main()’:
answer.code:95:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   95 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
answer.code:96:37: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   96 |     for (int i=1; i<=n; i++) { scanf("%d", &a[i]); }
      |                                ~~~~~^~~~~~~~~~~~~
answer.code:97:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   97 |     scanf("%d", &m);
      |     ~~~~~^~~~~~~~~~
answer.code:99:27: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   99 |         int x, y, c; scanf("%d %d %d", &x, &y, &c);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~