void build()
{
    int top=0;
    for(int i=1;i<=n;i++)
    {
        int k=top;
        while(k>0&&a[stk[k]]>a[i]) k--;
        if(k) rs[stk[k]]=i;
        if(k<top) ls[i]=stk[k+1];
        stk[++k]=i;
        top=k;
    }
}

事實上，stk[1]為棧底，即笛卡爾樹的根。