#include<bits/stdc++.h>
#include "rotate.h"
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 2e5 + 7, mid = 25e3, MOD = 5e4;
void energy(int n, vector<int> v)
{
vector<ii> tmp;
for (int i = 0; i < n; i++)
tmp.push_back({v[i], i});
sort(tmp.begin(), tmp.end());
deque<ii> dq[2];
for (ii i : tmp)
{
if (i.fi < mid)
dq[0].push_back(i);
else
dq[1].push_back(i);
}
while (1)
{
int check = 0;
for (int j = 0; j <= 1; j++)
{
if (dq[j].size() <= (n + 1) / 2 && (dq[j].size() && dq[j].back().fi == mid * j))
check++;
}
if (check == 2)
break;
if (dq[0].size() == dq[1].size())
{
int mn = min(mid - dq[0].back().fi, MOD - dq[1].back().fi);
vector<int> id;
for (int j = 0; j <= 1; j++)
{
id.push_back(dq[j].back().se);
dq[j].back().fi += mn;
if (dq[j].back().fi >= mid * (j + 1))
{
dq[j ^ 1].push_front({dq[j].back().fi % MOD, id.back()});
dq[j].pop_back();
}
}
rotate(id, mn);
continue;
}
if (dq[0].size() > dq[1].size())
{
vector<int> id;
id.push_back(dq[0].back().se);
//cerr << id[0] << " " << mid - dq[0].back().fi << '\n';
rotate(id, mid - dq[0].back().fi);
dq[1].push_front({mid, id[0]});
dq[0].pop_back();
}
else
{
vector<int> id;
id.push_back(dq[1].back().se);
//cerr << id[0] << " " << MOD - dq[1].back().fi << '\n';
rotate(id, MOD - dq[1].back().fi);
dq[0].push_front({0, id[0]});
dq[1].pop_back();
}
}
}
