IOIT rollercoaster2 - 0p

#include <bits/stdc++.h>
#define int long long
#define ABS(x) ((x) >= 0 ? (x) : -(x))

using namespace std;

const int INF = 1e16L;

void min_self(int &a, int b) {
    a = min(a, b);
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;
    vector<int> a(N + 1);
    for(int i = 1; i <= N; ++i)
        cin >> a[i];
    vector<vector<int>> dp(N + 1, vector<int>(8192, INF));
    for(int i = 0; i < 6000; ++i) {
        dp[1][i] = ABS(a[1] - i) * ABS(a[1] - i);
        if(i > 0)
            min_self(dp[1][i], dp[1][i - 1]);
    }
    for(int i = 2; i <= N; ++i) {
        if(!(i & 1))
            for(int j = 5999; j > 0; --j) {
                dp[i][j] = dp[i - 1][j - 1] + ABS(j - a[i]) * ABS(j - a[i]);
                min_self(dp[i][j], dp[i][j + 1]);
            }
        else
            for(int j = 1; j < 6000; ++j) {
                dp[i][j] = dp[i - 1][j + 1] + ABS(j - a[i]) * ABS(j - a[i]);
                if(j > 1)
                    min_self(dp[i][j], dp[i][j - 1]);
            }
    }
    int ans = INF;
    for(int j = 1; j < 6000; ++j)
        min_self(ans, dp[N][j]);
    dp = vector<vector<int>>(N + 1, vector<int>(8192, INF));
    for(int i = 5999; i > 0; --i) {
        dp[1][i] = ABS(a[1] - i) * ABS(a[1] - i);
        min_self(dp[1][i], dp[1][i + 1]);
    }
    for(int i = 2; i <= N; ++i) {
        if(i & 1)
            for(int j = 5999; j > 0; --j) {
                dp[i][j] = dp[i - 1][j - 1] + ABS(j - a[i]) * ABS(j - a[i]);
                min_self(dp[i][j], dp[i][j + 1]);
            }
        else
            for(int j = 1; j < 6000; ++j) {
                dp[i][j] = dp[i - 1][j + 1] + ABS(j - a[i]) * ABS(j - a[i]);
                if(j > 1)
                    min_self(dp[i][j], dp[i][j - 1]);
            }
    }
    for(int j = 1; j < 6000; ++j)
        min_self(ans, dp[N][j]);
    cout << ans;
}