#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 pt {
    ll x, y;
    pt() {}
    pt(ll _x, ll _y) : x(_x), y(_y) {}
    pt operator- (const pt &p) const {
        return pt(x - p.x, y - p.y);
    }
    ll operator% (const pt &p) const {
        return 1LL * x * p.x + 1LL * y * p.y;
    }
    ll operator* (const pt &p) const {
        return 1LL * x * p.y - 1LL * y * p.x;
    }
};

struct convex {
    int cur = 0;
    vector<pt> a{{-1, 1}};

    void add(pt p) {
        while (a.size() > 2) {
            pt last = a[a.size() - 1];
            pt prev = a[a.size() - 2];
            if (((p - last) * (last - prev)) >= 0) {
                a.pop_back();
                if (cur == a.size()) {
                    cur--;
                }
            } else break;
        }
        a.push_back(p);
    }

    ll get(pt v) {
        if (a.empty()) return INF;
        while (cur + 1 < (int)a.size()) {
            if ((a[cur + 1] % v) <= (a[cur] % v)) {
                cur++;
            } else {
                break;
            }
        }
        return a[cur] % v;
    }
};

struct fenwick {
    int n;
    vector<convex> a;

    fenwick(int _n) : n(_n) {
        a.resize(n);
    }

    void add(int x, pt p) {
        for (; x < n; x |= x + 1) {
            a[x].add(p);
        }
    }

    ll get(int x, pt v) {
        ll ans = INF;
        for (; x >= 0; x = (x & (x + 1)) - 1) {
            ans = min(ans, a[x].get(v));
        }
        return ans;
    }
};

ll solve(vector<int> a) {
    int n = a.size();

    auto v = a;
    sort(v.begin(), v.end());
    fenwick f(n);

    vector<ll> dp(n, INF);
    for (int j = 0; j < n; j++) {
        int id = lower_bound(v.begin(), v.end(), a[j]) - v.begin();
        pt v(-2 * (j - 1), 1);

        ll best = f.get(id, v);
        dp[j] = min(dp[j], best + sqr(j - 1));

        pt p(j, dp[j] + sqr(j));
        f.add(id, p);
    }

    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));
}