#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n;
vector<int> v;
vector<int> pos;
vector<array<int, 2>> a;
void rotate(vector<int> t, int x);
void prepare(int nn, vector<int> vv) {
n = nn; v = vv; pos.resize(n);
for (int i = 0; i < v.size(); i ++) a.push_back({v[i], i});
sort(a.begin(), a.end());
for (int i = 0; i < v.size(); i ++) v[i] = a[i][0], pos[i] = a[i][1];
}
void sub1() {
for (int i = 0; i < v.size() / 2; i ++)
rotate({pos[i]}, 100000 - v[i]);
for (int i = v.size() / 2; i < v.size(); i ++)
rotate({pos[i]}, 25000 - v[i]);
return;
}
ll cal(vector<int> v) {
ll res = 0;
for (int i = 0; i < (int)v.size(); i ++) {
for (int j = i + 1; j < (int)v.size(); j ++) {
int d = abs(v[i] - v[j]);
res += min(d, 50000 - d);
}
} return res;
}
void energy(int nn, vector<int> vv) {
prepare(nn, vv);
if (v.back() <= 25000) {sub1(); return;}
{
vector<int> v;
for (int i = 0; i < n; i ++) v.push_back(i);
rotate(v, 0 - v[0] + 100000);
for (int i = n - 1; i >= 0; i --) ::v[i] -= ::v[0];
}
ll old_value = cal(v); bool ok = false;
for (;;) {
if (v.back() <= 25000) break;
if (ok) return; ok = true;
// for (auto x: v) cout << x << ' '; cout << endl; cout << ok << endl;
for (int i = 0; i < n; i ++) {
vector<int> cur = v; int start = 0;
if (i != 0) start = max(start, v[i - 1]);
for (int j = start; j <= v[i] - 1; j ++) {
cur[i] = j; ll new_value = cal(cur);
if (new_value < old_value) {cur[i] = v[i]; continue;}
rotate({pos[i]}, j - v[i] + 100000);
v[i] = j, old_value = new_value, ok = false;
break;
}
}
}
// for (auto x: v) cout << x << ' '; cout << endl;
for (int i = 0; i < n / 2; i ++) rotate({pos[i]}, 0 - v[i] + 100000);
for (int i = n / 2; i < n; i ++) rotate({pos[i]}, 25000 - v[i] + 100000);
}
