#include<bits/stdc++.h>

 #define N 1000005

 #define ll long long

 using namespace std;

 ll sum[N],f[N];

 int n,q[N],a[N];

 inline char gc(){

     static char s[],*p1,*p2;

     if(p1==p2)p2=(p1=s)+fread(s,,,stdin);

     if(p1==p2)return EOF;return *p1++;

 }

 inline int read(){

     int x=;char ch=gc();

     while(ch<''||ch>'')ch=gc();

     while(ch<=''&&ch>='')x=x*+ch-'',ch=gc();

     return x;

 }

 ll U(int k,int j){return f[j]+sum[j]-f[k]-sum[k];}

 int D(int k,int j){return j-k;}

 int main(){

     n=read();

     for(register int i=;i<=n;++i){

         a[i]=read();

         sum[i]=sum[i-]+i;

     }

     int h=,t=,j;

     for(register int i=;i<=n;++i){

         while(h<t&&D(q[h],q[h+])*i>=U(q[h],q[h+]))++h;

         j=q[h];f[i]=f[j]+1ll*(i-j)*i-sum[i]+sum[j]+a[i];

         while(h<t&&U(q[t],q[t-])*D(i,q[t])>=U(i,q[t])*D(q[t],q[t-]))--t;

         q[++t]=i;

     }

     printf("%lld\n",f[n]);

     return ;

 }