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

using ll = long long;
const ll INF = 1e18;

ll sqr(ll x) {
    return x * x;
}

ll slow(vector<int> a) {
    int n = a.size();
    vector<ll> dp(n, INF);
    for (int i = 0; i < n; i++) dp[i] = sqr(i);

    for (int j = 1; j < n; j++) {
        for (int i = 0; i < j; i++) {
            if (a[i] <= a[j]) {
                dp[j] = min(dp[j], dp[i] + sqr(j - i - 1));
            }
        }
    }
    ll ans = INF;
    for (int i = 0; i < n; i++) {
        ans = min(ans, dp[i] + 1LL * sqr(n - 1 - i));
    }
    return ans;
}

struct line {
    ll k, b;
    line() : k(0), b(INF) {}
    line(ll _k, ll _b) : k(_k), b(_b) {}
    ll eval(ll x) {
        return k * x + b;
    }
};

struct segtree {
    int n;
    vector<line> t;

    segtree(int _n) {
        n = _n;
        t.resize(4 * n);
    }

    void add(line x) {
        int v = 1;
        int tl = 0, tr = n - 1;
        while (1) {
            int tm = (tl + tr) >> 1;

            if (x.eval(tm) < t[v].eval(tm)) swap(x, t[v]);

            bool betterL = x.eval(tl) < t[v].eval(tl);
            bool betterR = x.eval(tr) < t[v].eval(tr);
            assert(!betterL || !betterR);
            if (betterL) {
                v = v * 2;
                tr = tm;
            } else if (betterR) {
                v = v * 2 + 1;
                tl = tm + 1;
            } else {
                break;
            }
        }
    }

    ll get(int x) {
        ll ans = INF;
        int v = 1;
        int tl = 0, tr = n - 1;
        while (1) {
            ans = min(ans, t[v].eval(x));
            if (tl == tr) break;
            int tm = (tl + tr) >> 1;
            if (x <= tm) {
                v = v * 2;
                tr = tm;
            } else {
                v = v * 2 + 1;
                tl = tm + 1;
            }
        }
        return ans;
    }
};

ll solve(vector<int> a) {
    int n = a.size();
    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int i, int j) {
        return a[i] < a[j] || a[i] == a[j] && i < j;
    });

    segtree tr(n);
    vector<ll> dp(n, INF);
    for (int j : id) {
        dp[j] = min(sqr(j), tr.get(j) + sqr(j - 1));
        tr.add(line(-2 * j, dp[j] + sqr(j) + 2 * j));
    }

    ll ans = INF;
    for (int i = 0; i < n; i++) {
        ans = min(ans, dp[i] + sqr(n - 1 - i));
    }
    return ans;
}

void stress() {
    for (int it = 0;; it++) {
        mt19937 rnd(it);
        cerr << it << endl;

        int n = rnd() % 100 + 1;
        vector<int> a(n);
        for (int i = 0; i < n; i++) a[i] = rnd() % n + 1;

        auto ans1 = solve(a);
        auto ans2 = slow(a);
        if (ans1 != ans2) {
            cout << ans1 << " instead of " << ans2 << endl;
            cout << n << endl;
            for (int x : a) cout << x << " ";
            cout << endl;
            exit(0);
        }
    }
}

int main() {
//    stress();

    int n;
    scanf("%d", &n);
    vector<int> a(n);
    for (int &x : a) scanf("%d", &x);

    printf("%lld\n", solve(a));
}