#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

const int N = 1e6+,inf = 2e9, mod = 1e9+;

typedef long long ll;

ll dp[N];

ll n,a[N],b[N];

double getsum(ll k,ll j)

{

    return (double)((dp[k]-dp[j]) + (double)(k*k+k-j*j-j)/2.0)/(double)(k-j);

}

int main()

{

    scanf("%lld",&n);

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

    {

        scanf("%lld",&b[i]);

    }

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

    {

        a[i]=b[n-i+];

    }

    deque<int > q;

    dp[] = a[];

    q.push_back();

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

    {

        int now=q.front();q.pop_front();

        while(!q.empty()&&getsum(q.front(),now)<i) now=q.front(),q.pop_front();

        q.push_front(now);

        dp[i] = dp[now] + (ll)(i-now-)*(ll)(i-now)/ + a[i];

        now = q.back();q.pop_back();

        while(!q.empty()&&getsum(i,now)<getsum(now,q.back())) now=q.back(),q.pop_back();

        q.push_back(now);

        q.push_back(i);

    }

    ll ans=1e18;

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

        ans=min(ans,dp[i]+(ll)(n-i)*(n-i+)/);

    printf("%lld\n",ans);

    return ;

}