学步园

#include<iostream>
#include<cstdio>
using namespace std;
inline long long read(){  
    long long 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;  
}  
long long f[1000001],ans,n,a[1000001],q[1000001],t,w;
inline double calc(long long k,long long j){
	return (double)((2.0*(f[k]-f[j])+k*(k+1)-j*(j+1))/(2*k-2*j));
}
int main(){
	n=read();
	for(int i=n;i>=1;i--)
		a[i]=read();
	t=w=1;f[1]=a[1];q[1]=1ll;  
	ans=a[1]+1ll*n*(n-1)/2ll;  
	for(int i=2;i<=n;i++){
		while(t<w&&calc(q[t+1],q[t])<i)t++;
		f[i]=f[q[t]]+(long long)((i-q[t])*(i-q[t]-1)/2+a[i]);
		ans=min(ans,f[i]+(long long)((n-i+1)*(n-i)/2));
		while(t<w&&calc(q[w],q[w-1])>calc(i,q[w]))w--;
		q[++w]=i;
	}
	printf("%lld",ans);
}