#include <bits/stdc++.h>
using namespace std;
using ld = long double;
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];
}
auto get_sum_excl = [&](int L, int R, int excl_pos, int excl_val) {
L = (L % 50000 + 50000) % 50000;
R = (R % 50000 + 50000) % 50000;
int res = 0;
if (L <= R) {
res = pref[R] - (L == 0 ? 0 : pref[L - 1]);
if (L <= excl_pos && excl_pos <= R) res -= excl_val;
} else {
res = pref[49999] - (L == 0 ? 0 : pref[L - 1]) + pref[R];
if (excl_pos >= L || excl_pos <= R) res -= excl_val;
}
return res;
};
while (true) {
int col = 0;
for (int i = 0; i + 1 < 50000; i++) {
if (cnt[i] == 0) continue;
int l = 1, r = 49999 - i;
int best_d = 0;
while (l <= r) {
int mid = l + (r - l) / 2;
int curr = i + mid - 1;
int x = get_sum_excl(curr + 1, curr + 25000, i, cnt[i]);
int y = n - x - cnt[i];
if (x <= y) {
best_d = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
if (best_d > 0) {
col++;
cnt[i + best_d] += cnt[i];
for (int k = i; k < i + best_d; k++) {
pref[k] -= cnt[i];
}
rotate(pos[i], best_d);
for (auto c : pos[i]) pos[i + best_d].push_back(c);
pos[i].clear();
cnt[i] = 0;
}
}
if (col == 0) break;
}
while (true) {
int col = 0;
for (int i = 49999; i - 1 >= 0; i--) {
if (cnt[i] == 0) continue;
int l = 1, r = i;
int best_d = 0;
while (l <= r) {
int mid = l + (r - l) / 2;
int curr = i - mid + 1;
int x = get_sum_excl(curr - 25000, curr - 1, i, cnt[i]);
int y = n - x - cnt[i];
if (x <= y) {
best_d = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
if (best_d > 0) {
col++;
cnt[i - best_d] += cnt[i];
for (int k = i - best_d; k < i; k++) {
pref[k] += cnt[i];
}
rotate(pos[i], 50000 - best_d);
for (auto c : pos[i]) pos[i - best_d].push_back(c);
pos[i].clear();
cnt[i] = 0;
}
}
if (col == 0) break;
}
}
