PROGRESS

#define task "PROGRESS"

#include <iostream>
#include <cstdio>
#include <functional>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 1e5 + 5;
constexpr ll Inf = 1e17;
struct Point
{
    ll x, y;
    Point(ll x = 0, ll y = 0) : x(x), y(y) {}
    Point operator-(const Point &a) const
    {
        return Point(x - a.x, y - a.y);
    }
    ll operator*(const Point &a)
    {
        return x * a.y - y * a.x;
    }
    bool operator<(const Point &a)
    {
        return x < a.x || (x == a.x && y < a.y);
    }
} a[N], b[N], pos[N];

int n, m, id[N];
ll sum(0);

void Read()
{
    cin >> n;
    if (n == 1)
    {
        cout << 0;
        exit(0);
    }
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i].y;
        a[i].x = i - 1;
        sum += a[i].y;
    }
}
/// Tìm tiếp điểm
int Get(ll v)
{
    Point tmp = Point(1, v);
    int l = 1, mid, h = m;

    while (l <= h)
    {
        mid = (l + h) / 2;
        if ((b[mid + 1] - b[mid]) * tmp < 0)
            l = mid + 1;
        else
            h = mid - 1;
    }

    return l;
}
/// Chặt tam phân, tìm hệ số góc
ll Cal(ll l, ll h, int j)
{
    function<ll(ll)> f = [&](ll v)
    {
        return 1ll * n * (n - 1) / 2 * v - sum + (b[j].y - v * b[j].x) * n;
    };

    --h;
    while (l <= h)
    {
        ll mid = (l + h) / 2;

        if (f(mid + 1) < f(mid))
            l = mid + 1;
        else
            h = mid - 1;
    }

    return f(l);
}

void Solve()
{
    ll ans(Inf);

    for (int i = 1; i <= n; ++i)
    {
        while (m > 1 && (b[m - 1] - a[i]) * (b[m] - a[i]) >= 0)
            --m;
        b[++m] = a[i];
    }

    b[m + 1] = Point(b[m].x, 0);

    for (ll x = 1e9; x >= -1e9;)
    {
        int j = Get(x);

        ll l = -1e9, mid, h = x;
        while (l <= h)
        {
            mid = (l + h) / 2;
            if (Get(mid) == j)
                h = mid - 1;
            else
                l = mid + 1;
        }

        ans = min(ans, Cal(l, x, j));

        x = h;
    }

    cout << ans;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }
    Read();
    Solve();
}
/*
4
1 5 5 6
9
9 8 7 6 5 4 3 2 2
*/