#include <bits/stdc++.h>
using namespace std;

constexpr bool debug_convex=false;
constexpr bool debug_fenwick=false;
constexpr bool debug_dp=false;
constexpr bool debug_lines=false;

constexpr int MAXV=1'000'000;

struct Line{
    int64_t c,m;

    int64_t eval(int x){
        return m*x+c;
    }
};

/**
 * Line equations ordered by monotonically-decreasing gradient.
 * For any call to insert({c,m}), m<=o.m for all other lines o.
 *
 * Thus any newly-inserted line is optimal for x=infinity, and
 * we only have to remove previous lines that have no optimum x
 * any more.
 */
struct Lines{
    deque<Line> h;

    void insert(Line const &l){
        while (h.size()>=1){
            int const n=h.size();
            if (n>=1 and h.back().c>=l.c){
                h.pop_back();
                continue;
            }
            if (n>=2){
                auto const &a=h[n-2];
                auto const &b=h[n-1];
                // a.c+a.m*x = b.c+b.m*x
                // (a.m-b.m)*x = b.c-a.c
                // x = (b.c-a.c)*(a.m-b.m)
                // if ((b.c-a.c)/(a.m-b.m) >= (l.c-b.c)/(b.m-l.m)){
                if ((b.c-a.c)*(b.m-l.m) >= (l.c-b.c)*(a.m-b.m)){
                    h.pop_back();
                    continue;
                }
            }
            break;
        }
        h.push_back(l);
    }

    int64_t advance(int64_t x){
        if (debug_convex){
            int64_t best=h.front().eval(x);
            for (auto i: h) best=min(best,i.eval(x));
            return best;
        }else{
            while (h.size()>1 and h[1].eval(x)<=h[0].eval(x)){
                h.pop_front();
            }
            return h.front().eval(x);
        }
    }
};

vector<Lines> fen;

// Add line `l` to set `y`
void fenwick_insert(int y,Line const &l){
    for (; y<=MAXV; y|=y+1){
        fen[y].insert(l);
    }
}

// Search sets [0, y] for line with minimum eval(x)
// Calls must be in increasing order of x.
int64_t fenwick_least(int y,int x){
    int64_t res=INT64_MAX;
    for (; y>=0; --(y&=y+1)){
        res=min(res,fen[y].advance(x));
    }
    return res;
}

int main(){
    int n; cin>>n;
    vector<int64_t> v(n); for (auto &i: v) cin>>i;
    v.push_back(MAXV);
    fen.resize(MAXV+1);

    vector<int64_t> dp(n+2);
    vector<Line> lines(n+2);

    lines[0]={0, 0};
    fenwick_insert(0, lines[0]);

    for (int64_t i=0; i<=n; i++){
        if (debug_fenwick){
            for (int64_t j=-1; j<i; j++){
                if (j==-1 or v[j]<=v[i] and lines[j+1].eval(i)<dp[i+1]){
                    dp[i+1]=lines[j+1].eval(i);
                }
            }
            dp[i+1]=i*i+dp[i+1];
        } else {
            dp[i+1]=i*i+fenwick_least(v[i],i);
        }

        lines[i+1]={dp[i+1]+(i+1)*(i+1), -2*(i+1)};
        fenwick_insert(v[i],lines[i+1]);

        if (debug_dp){
            cerr<<" dp["<<i+1<<"] = "<<dp[i+1]<<endl;
        }
        if (debug_lines){
            cerr<<"   line["<<i+1<<"] = "<<lines[i+1].c<<"+x*"<<lines[i+1].m<<endl;
        }
    }

    cout<<dp.back()<<endl;
}