看了一圈题解，似乎时间复杂度都在 $\Theta(2n)$ 以上，但是理论上这道题是可以实现 $\Theta(n)$ ，在一遍读入过程中就处理完的。
以下核心代码可以实现这一点：

int i,c,n,ans,R;
void solve(int x=0,int h=5001)
{
    int d=0,r=0,m=0,t=x,p=x;
    if(c<n)
    {
        cin>>i;
        while(i<h)
        {
            if(c==n)
            {
                if(h==5001)cout<<ans<<endl;
                else ans+=r-(p-x)*(h-m);
                return;
            } 
            d=i,++c,solve(c,i),c<n?i>=m?m=i,p=c:1,r+=(h-d)*(c-t),t=c:1;
        }
        if(i>=h)
        {
            r+=(h-d)*(c-t);
            ans+=r;
            return;
        }
    }
}

我没在题解中找到这个做法，是我没有看见还是的确没有这个思路？
如果的确没有这个方法的话，我请求重新开放题解通道。