$$S_i = \sum_{j=1}^{n-i+1}j$$

$$dp_i = min(dp_j + S_{j+1} - S_{i+1} - (i-j)\times(n-i+1)+a_i)\ \ j\in [1,i-1]$$

$$dp_i = min(dp_j + S_{j+1} - (i-j)\times(n-i+1))-S_{i+1}+a_i\ \ j\in [1,i-1]$$

$$dp_i = min(dp_j + S_{j+1} +j\times(n-i+1))-S_{i+1}+a_i-i\times(n-i+1)\ \ j\in [1,i-1]$$

设 $k<j<i$,若节点 $j$ 比节点 $k$ 优:
$$dp_j+S_{j+1}+j\times(n-i+1)\le dp_k+S_{k+1}+k\times(n-i+1)$$

$$(dp_j+S_{j+1})-(dp_k+S_{k+1})\le (-j+k)\times (n-i+1)$$

$${(dp_j+S_{j+1})-(dp_k+S_{k+1})\over{(-j+k)}}\le(n-i+1)$$

$$令y_i=dp_i+S_i,\ \ x_i=-i$$

$${{y_j-y_k}\over{x_j-x_k}}\le (n-i+1)$$

代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 1000005
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int n;
static LL a[N], dp[N];
static int q[N], h, t;

inline LL S(LL i) {
    i = n - i + 1;
    return ((LL)(i + 1) * (LL)i) >> 1;
}

LL getDP(LL i, LL j) { return dp[j]-S(i+1)-(i-j)*(n-i+1)+S(j+1)+a[i]; }

LL UP(LL j, LL k) { return (dp[j]+S(j+1))-(dp[k]+S(k+1)); }

LL DOWN(LL j, LL k) { return (-j + k); }

int main() {
    n = read();
    for(int i=1; i<=n; i++) a[i]=read();
    
    for(int i=1; i<=n; i++) {
        while(t>h && UP(q[h+1],q[h])<=(LL)(n-i+1)*DOWN(q[h+1],q[h])) h++;
        dp[i] = getDP(i, q[h]);
        while(t>h && UP(i,q[t])*DOWN(q[t],q[t-1])>UP(q[t],q[t-1])*DOWN(i,q[t])) t--;
        q[++t] = i;
    }
    printf("%lld", dp[n]);
        
    return 0;
}