三分

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;

int n;
long long a[maxn], b[maxn];

__int128 ans = 1e30;

void output(__int128 a) {
    if (a / 10 > 0)
        output(a/10);
    int x = a % 10;
    printf("%d", x);
}

__int128 cal(long long d) {
    for (int i = 1; i <= n; i++)
        b[i] = a[i] - i * d;
    sort(b+1, b+n+1);
    __int128 res = 0;
    for (int i = 1, j = n; i < j; i++, j--)
        res += b[j] - b[i];
    return res;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", a+i);
    sort(a+1, a+n+1);
    long long l = 0, r = 1e12;
    while (r - l >= 10) {
        long long mid1 = (2*l+r)/3, mid2 = (l+2*r)/3;
        __int128 tmp1 = cal(mid1), tmp2 = cal(mid2);
        ans = min({ans, tmp1, tmp2});
        if (tmp1 < tmp2) r = mid2;
        else l = mid1;
    }
    // [l,r]
    for (int i = l; i <= r; i++)
        ans = min(ans, cal(i));
    output(ans);
    return 0;
}