#include "rotate.h"
#include <vector>
using namespace std;
typedef vector<int> vi;
const int N = 100000, X = 50000;
unsigned int Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
int xx[N], ii[N], jj[N];
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (xx[ii[j]] == xx[i_])
j++;
else if (xx[ii[j]] < xx[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
void energy(int n, vi xx_) {
for (int i = 0; i < n; i++)
xx[i] = xx_[i];
for (int i = 0; i < n; i++)
ii[i] = i;
sort(ii, 0, n);
int k = 0;
while (k < n && xx[ii[k]] < X / 2)
k++;
if (k > n / 2) {
for (int i = 0; i < n; i++)
xx[i] = (xx[i] + X / 2) % X;
for (int i = 0; i < n; i++)
jj[i] = ii[(i + k) % n];
for (int i = 0; i < n; i++)
ii[i] = jj[i];
}
for (int g = 0; g < n / 2; g++) {
int i = ii[g];
if (xx[i] >= X / 2)
rotate({ i }, X - (xx[i] - X / 2 + 1)), xx[i] = X / 2 - 1;
}
for (int h = n / 2; h < n; h++)
xx[ii[h]] -= X / 2;
int g = 0, h = n / 2;
while (g < n / 2 || h < n)
if (h == n || g < n / 2 && xx[ii[g]] < xx[ii[h]]) {
if (g < h - n / 2)
rotate({ ii[g] }, X - (xx[ii[g]] - xx[ii[g + n / 2]]));
g++;
} else {
if (h - n / 2 < g)
rotate({ ii[h] }, X - (xx[ii[h]] - xx[ii[h - n / 2]]));
h++;
}
}
