#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]]++;
}
vector<int> pref(50000);
pref[0] = cnt[0];
for (int i = 1; i < 50000; i++) {
pref[i] = pref[i - 1] + cnt[i];
}
while (true) {
int col = 0;
for (int i = 0; i + 1 < 50000; i++) {
if (cnt[i] == 0) continue;
int x = 0;
if (i + 25000 < 50000) {
x = pref[i + 25000] - pref[i];
} else {
x = pref[49999] - pref[i] + pref[i + 25000 - 50000];
}
int y = n - x - cnt[i];
if (x <= y) {
col++;
cnt[i + 1] += cnt[i];
pref[i] -= cnt[i];
cnt[i] = 0;
rotate(pos[i], 1);
for (auto c : pos[i]) pos[i + 1].push_back(c);
pos[i].clear();
}
}
for (int i = 49999; i - 1 >= 0; i--) {
if (cnt[i] == 0) continue;
int x = 0;
if (i - 25000 >= 0) {
x = pref[i - 1];
if (i - 25000 - 1 >= 0) x -= pref[i - 25000 - 1];
} else {
x = pref[i - 1];
x += pref[49999] - pref[i - 25000 + 50000 - 1];
}
int y = n - x - cnt[i];
if (x <= y) {
col++;
cnt[i - 1] += cnt[i];
pref[i - 1] += cnt[i];
cnt[i] = 0;
rotate(pos[i], 49999);
for (auto c : pos[i]) pos[i - 1].push_back(c);
pos[i].clear();
}
}
if (col == 0) break;
}
}
/*int main() {
int n;
cin >> n;
v.resize(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
energy(n);
}*/
