rt，和题解对拍拍不出来

#include <bits/stdc++.h>
#define MISAKA main
#define ll long long
using namespace std;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
const double eps=1e-9;
const int N=2e5+10,inf=1e9,mod=998244353;
struct node{int ls,rs;ll mx,tag;}t[N<<5];
int cnt=0,n,m,a[N],rt[N],lson[N],rson[N],s[N],top=0;ll mxa,mxb,lim,sum=0;
struct Node{int x,y;};vector<Node> v[N];
void cal(int now,ll x){t[now].tag+=x,t[now].mx+=x;}
void pushdown(int now){
    int ls=t[now].ls,rs=t[now].rs,tag=t[now].tag;
    if(ls) cal(ls,tag);if(rs) cal(rs,tag);t[now].tag=0;
}
ll qry(int now,int x,int L,int R){
    if(!now||L>x) return 0;
    if(R<=x) return t[now].mx;
    pushdown(now);int mid=L+R>>1;
    return max(qry(t[now].ls,x,L,mid),qry(t[now].rs,x,mid+1,R));
}
void upd(int &now,int x,ll k,int L,int R){
    if(!now) now=++cnt;t[now].mx=max(t[now].mx,k);
    if(L==R) return;int mid=L+R>>1;
    if(x<=mid) upd(t[now].ls,x,k,L,mid);
    else upd(t[now].rs,x,k,mid+1,R);
}
int merge(int a,int b,int L,int R){
    if(!a&&!b) return 0;
    if(!a||!b){
        if(b) mxb=max(mxb,qry(b,lim,L,R)),cal(b,mxa);
        else mxa=max(mxa,qry(a,lim,L,R)),cal(a,mxb);
        return a|b;
    }
    if(L==R){
        if(R<=lim) mxa=max(mxa,t[a].mx),mxb=max(mxb,t[b].mx);
        t[a].mx=max(t[a].mx+mxb,t[b].mx+mxa);return a;
    }
    pushdown(a);pushdown(b);int mid=L+R>>1;
    t[a].ls=merge(t[a].ls,t[b].ls,L,mid);
    t[a].rs=merge(t[a].rs,t[b].rs,mid+1,R);
    t[a].mx=max(t[t[a].ls].mx,t[t[a].rs].mx);
    return a;
}
void dfs(int u){
    for(auto [y,c]:v[u]) upd(rt[u],y,c,1,n);int ls=lson[u],rs=rson[u];
    if(ls) dfs(ls),lim=a[u],mxa=mxb=0,rt[u]=merge(rt[u],rt[ls],1,n);
    if(rs) dfs(rs),lim=a[u],mxa=mxb=0,rt[u]=merge(rt[u],rt[rs],1,n);
}
signed MISAKA(){
    n=read();int root=1;s[top=1]=1;
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=2;i<=n;i++){
        while(top&&a[s[top]]<a[i]) top--;
        if(!top) lson[i]=s[1],root=i;
        else lson[i]=rson[s[top]],rson[s[top]]=i;
        s[++top]=i;
    }
    m=read();
    for(int i=1;i<=m;i++){
        int x=read(),y=read(),c=read();
        v[x].push_back(Node{y,c});sum+=c;
    }
    dfs(root);printf("%lld",sum-t[rt[root]].mx);
    return 0;
}