作为勤劳的题解自动姬来写这篇题解。

仅我自己认为，想到凸包的过程是这道题的难点，凸包以后容易解决，相反不是难点。所以这篇题解会主要讲解如何想到凸包的过程。

假设 $a_i\lt a_j(i\lt j)$。首先注意到最基本的情况，即 $n=j-i+1=2^k+1,a_j=a_i+p2^k$，序列容易调整至 $a_p=a_i+(p-1)2^k$ 的形态。

接下来处理特殊情况 $a_j=a_i+p2^k+r(r\in[0,2^k))$，容易发现能调整到差分数组形如 $p,\dots,p,p+1,\dots,p+1$。

那我们便猜测对于任意的 $i,j(i\lt j)$，是否都可以满足可以调整到差分数组形如 $p,\dots,p,p+1,\dots,p+1$。事实证明是可以满足的。对于差分数组 $b$，若存在 $pos$ 满足 $b_{pos+1}-b_{pos}\ge 2$，那么必然可以将实际中间的数调整到更小。最终总是可以调整到形如 $p,\dots,p,p+1,\dots,p+1$。而这个形态也是最优的，因为此时差分数组并不存在 $|b_i-b_{i-1}|\ge 2$。由于这里不是 MO 性质的题目，所以不放严格证明，读者可以试着自证。

那也就是需要找到一个长度为 $l$ 的序列 $A$，使得 $A_1=1,A_l=n,\forall i\in[1,l),A_i\lt A_{i+1}$。而对于每一段 $[A_i,A_{i+1}]$，形如上文的形式调整。将其视作平面问题，类似有 $l-1$ 段线段拼接在一起。可是要如何找到最优的答案呢？对于某些决策 $i,j,k(i\lt j\lt k)$，$\text{trans}(i,k)$ 优于 $\text{trans}(i,j),\text{trans}(j,k)$ 的充要条件在平面上大致可看做是 $\text{slope}(a_i,a_j)\gt\text{slope}(a_j,a_k)$，即形成了上凸包，显然可以消掉凸的部分使总和最小。那我们可以找到极优解即在任何一个子区间内没有上凸的部分。即下凸包。对于总体而言，我们需要找到这 $n$ 个点的近似下凸包。为什么说近似呢？因为这里的斜率判断是根据两段差分数组的首尾元素的大小。令 $K$ 和 $L$ 是相邻两个决策段，$pre_I$ 为第 $I$ 段的差分数组头元素，$suf_I$ 为第 $I$ 段的差分数组尾元素，那么 $K$ 和 $L$ 共存（即不用合成同一个决策段）的等价条件是 $suf_K\le pre_L$。

那么下凸包可以用一个单调栈简单维护。代码很好写，细节有点多，注意处理 corner case。

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e5+5;
int n;
ll a[N];
ll Abs(ll x){
    return max(x,-x);
}
ll slope(int i,int j,int type){
    ll k=Abs(a[i]-a[j]),l=j-i;
    ll res;
    if(a[i]<=a[j]){
        if(type==0){
            res=k/l;
        }else{
            res=(k+l-1)/l;
        }
    }else{
        if(type==0){
            res=-(k+l-1)/l;
        }else{
            res=-k/l;
        }
    }
    return res;
}
ll F(ll n){
    return n*(n+1)/2;
}
ll getsum(int i,int j){
    ll k=Abs(a[i]-a[j]),l=j-i,minn=min(a[i],a[j]);
    return minn*(l+1)+F(l)*(k/l)+F(k%l);
}
int sta[N],top;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    sta[++top]=1;
    for(int i=2;i<=n;i++){
        while(top>=2&&slope(sta[top-1],sta[top],1)>slope(sta[top],i,0)){
            --top;
        }
        sta[++top]=i;
    }
    ll res=0;
    for(int i=2;i<=top;i++){
        res+=getsum(sta[i-1],sta[i]);
    }
    for(int i=2;i<top;i++){
        res-=a[sta[i]];
    }
    printf("%lld\n",res);
    return 0;
}