#include "rotate.h"
#include <bits/stdc++.h>
using namespace std;
const int L = 50000;
struct BIT {
vector<int> cnt;
vector<long long> sum;
int n;
BIT(int sz) : n(sz), cnt(sz+1, 0), sum(sz+1, 0) {}
void add(int idx, int val) {
idx++; // 1-based
while (idx <= n) {
cnt[idx] += val;
sum[idx] += val * (idx-1);
idx += idx & -idx;
}
}
int query_cnt(int idx) {
if (idx < 0) return 0;
idx = min(idx, n-1);
idx++;
int res = 0;
while (idx > 0) { res += cnt[idx]; idx -= idx & -idx; }
return res;
}
long long query_sum(int idx) {
if (idx < 0) return 0;
idx = min(idx, n-1);
idx++;
long long res = 0;
while (idx > 0) { res += sum[idx]; idx -= idx & -idx; }
return res;
}
int range_cnt(int l, int r) {
if (l <= r) return query_cnt(r) - query_cnt(l-1);
else return query_cnt(L-1) - query_cnt(l-1) + query_cnt(r);
}
long long range_sum(int l, int r) {
if (l <= r) return query_sum(r) - query_sum(l-1);
else return query_sum(L-1) - query_sum(l-1) + query_sum(r);
}
};
double acute_sum(int x, BIT& bit) {
int l1 = x;
int r1 = (x + L/2 - 1) % L;
int cnt1 = bit.range_cnt(l1, r1);
long long sum1 = bit.range_sum(l1, r1);
long long contrib1 = sum1 - (long long)cnt1 * x;
int l2 = (x + L/2) % L;
int r2 = (x + L - 1) % L;
int cnt2 = bit.range_cnt(l2, r2);
long long sum2 = bit.range_sum(l2, r2);
long long contrib2 = (long long)cnt2 * (L + x) - sum2; // L - (y - x) = L + x - y
return contrib1 + contrib2;
}
void energy(int n, std::vector<int> v) {
vector<int> cur = v;
BIT bit(L);
for (int val : v) bit.add(val, 1);
vector<int> cnt(L, 0);
for (int val : v) cnt[val]++;
set<int> pts;
for (int i = 0; i < L; i++) if (cnt[i]) pts.insert(i);
auto gap_len = [&](int a, int b) {
return (b - a + L) % L;
};
using Gap = pair<int, int>;
priority_queue<Gap> max_gap;
priority_queue<Gap, vector<Gap>, greater<Gap>> min_gap;
auto update_gaps = [&]() {
// clear queues (lazy deletion will be used)
while (!max_gap.empty()) max_gap.pop();
while (!min_gap.empty()) min_gap.pop();
if (pts.size() <= 1) return;
for (auto it = pts.begin(); it != pts.end(); ++it) {
int a = *it;
auto nit = next(it);
if (nit == pts.end()) nit = pts.begin();
int b = *nit;
int len = gap_len(a, b);
max_gap.emplace(len, a);
min_gap.emplace(len, a);
}
};
update_gaps();
vector<vector<int>> rods_at(L);
for (int i = 0; i < n; i++) rods_at[cur[i]].push_back(i);
// function to try moving a rod from old_pos to new_pos
auto try_move = [&](int rod_idx, int old_pos, int new_pos) -> bool {
if (old_pos == new_pos) return false;
double old_contrib = acute_sum(old_pos, bit);
double new_contrib = acute_sum(new_pos, bit) - min(abs(new_pos - old_pos), L - abs(new_pos - old_pos));
double delta = new_contrib - old_contrib;
if (delta > 1e-9) {
rotate(vector<int>{rod_idx}, (new_pos - old_pos + L) % L);
// update data structures
bit.add(old_pos, -1);
bit.add(new_pos, 1);
cnt[old_pos]--;
if (cnt[old_pos] == 0) pts.erase(old_pos);
cnt[new_pos]++;
if (cnt[new_pos] == 1) pts.insert(new_pos);
// update rods_at
auto& vec_old = rods_at[old_pos];
vec_old.erase(remove(vec_old.begin(), vec_old.end(), rod_idx), vec_old.end());
rods_at[new_pos].push_back(rod_idx);
cur[rod_idx] = new_pos;
update_gaps();
return true;
}
return false;
};
const int MAX_ITER = 2000000 / n + 10; // each move costs 1 selection
for (int iter = 0; iter < MAX_ITER; ++iter) {
if (pts.size() <= 1) break;
// get largest gap
while (!max_gap.empty()) {
auto [len, a] = max_gap.top();
auto it = pts.find(a);
if (it == pts.end()) { max_gap.pop(); continue; }
auto nit = next(it); if (nit == pts.end()) nit = pts.begin();
int b = *nit;
if (gap_len(a, b) != len) { max_gap.pop(); continue; }
break;
}
if (max_gap.empty()) break;
auto [max_len, max_left] = max_gap.top();
while (!min_gap.empty()) {
auto [len, a] = min_gap.top();
auto it = pts.find(a);
if (it == pts.end()) { min_gap.pop(); continue; }
auto nit = next(it); if (nit == pts.end()) nit = pts.begin();
int b = *nit;
if (gap_len(a, b) != len) { min_gap.pop(); continue; }
break;
}
if (min_gap.empty()) break;
auto [min_len, min_left] = min_gap.top();
if (max_len - min_len <= 1) break; // close enough
int rod_pos = min_left;
if (rods_at[rod_pos].empty()) {
// try the right endpoint
auto it = pts.find(min_left);
auto nit = next(it); if (nit == pts.end()) nit = pts.begin();
rod_pos = *nit;
if (rods_at[rod_pos].empty()) continue; // shouldn't happen
}
int rod_idx = rods_at[rod_pos].back(); // pick one rod
auto it_max = pts.find(max_left);
auto nit_max = next(it_max); if (nit_max == pts.end()) nit_max = pts.begin();
int max_right = *nit_max;
int gap_start = max_left;
int gap_len_val = max_len;
vector<int> candidates;
candidates.push_back((gap_start + gap_len_val / 2) % L);
if (gap_len_val > 2) {
candidates.push_back((gap_start + gap_len_val / 4) % L);
candidates.push_back((gap_start + 3 * gap_len_val / 4) % L);
}
bool moved = false;
for (int new_pos : candidates) {
if (try_move(rod_idx, rod_pos, new_pos)) {
moved = true;
break;
}
}
if (!moved) {
int flip_pos = (rod_pos + 25000) % L;
if (try_move(rod_idx, rod_pos, flip_pos)) {
moved = true;
}
}
if (!moved) {
break;
}
}
}
