#include "rotate.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void energy(int n, vector<int> v) {
const ll mod = 50000;
vector<int> all(n);
iota(all.begin(), all.end(), 0);
sort(all.begin(), all.end(), [&](int a, int b) { return v[a] < v[b]; });
// vector<bool> used(n);
deque<int> left;
vector<int> right;
for (auto a : all) left.push_back(a);
while (!left.empty()) {
// int cur2 = left.back();
// if (used[left.back()]) {
// left.pop_back();
// continue;
// }
if (v[left.back()] - v[left[0]] > mod / 2) {
right.push_back(left.back());
left.pop_back();
} else
break;
}
while (left.size() + right.size() >= 2) {
if (left.empty()) {
left.push_back(right.back());
right.pop_back();
}
int cur = left.front();
// used[left.front()] = 1;
left.pop_front();
while (!right.empty()) {
if (v[right.back()] - v[cur] <= mod / 2) {
left.push_back(right.back());
right.pop_back();
} else
break;
}
if (left.size() >= right.size()) {
if (left.empty()) break;
rotate({cur}, (v[left.back()] - mod / 2 - v[cur] + mod) % mod);
// used[left.back()] = 1;
left.pop_back();
} else {
rotate({cur}, (v[right.back()] + mod / 2 - v[cur] + mod) % mod);
right.pop_back();
}
}
}
