#include <bits/stdc++.h>
using namespace std;
using ld = long double;
/*vector<int> v;
void rotate(std::vector<int> t, int x) {
for (int i = 0; i < t.size(); i++) {
v[t[i]] = (v[t[i]] + x) % 50000;
}
}*/
void rotate(std::vector<int> t, int x);
void energy(int n, vector<int> v) {
vector<vector<int>> pos(50000);
vector<int> cnt(50000);
for (int i = 0; i < n; i++) {
pos[v[i]].push_back(i);
cnt[v[i]]++;
}
for (int i = 1; i < 50000; i++) {
cnt[i] += cnt[i - 1];
}
int rf = -1;
for (int r = 25000; r < 50000; r++) {
int l = r - 25000 - 1;
int col = cnt[r];
if (l >= 0) col -= cnt[l];
if (col - 1 >= n - col) {
rf = r;
break;
}
}
if (rf == -1) return;
for (int i = rf; i >= rf - 25000; i--) {
int x = i - (rf - 25000);
rotate(pos[i], x);
for (auto j : pos[i]) {
v[j] = rf - 25000;
}
}
vector<pair<int, int>> a;
for (int i = 0; i < n; i++) {
if (v[i] < 25000) {
a.emplace_back(v[i], i);
}
}
sort(a.begin(), a.end());
int m = n / 2;
for (int i = 0; i < m; i++) {
if (a[i].first == 0) continue;
vector<int> t = {a[i].second};
int x = 50000 - a[i].first;
rotate(t, x);
}
for (int i = m; i < a.size(); i++) {
if (a[i].first == 25000) continue;
vector<int> t = {a[i].second};
int x = 25000 - a[i].first;
rotate(t, x);
}
}
/*int main() {
int n;
cin >> n;
v.resize(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
energy(n);
}*/
