#define _CRT_SECURE_NO_WARNINGS
/*
⣿⡟⡡⠾⠛⠻⢿⣿⣿⣿⡿⠃⣿⡿⣿⠿⠛⠉⠠⠴⢶⡜⣦⡀⡈⢿⣿
⡿⢀⣰⡏⣼⠋⠁⢲⡌⢤⣠⣾⣷⡄⢄⠠⡶⣾⡀⠀⣸⡷⢸⡷⢹⠈⣿
⡇⢘⢿⣇⢻⣤⣠⡼⢃⣤⣾⣿⣿⣿⢌⣷⣅⡘⠻⠿⢛⣡⣿⠀⣾⢠⣿
⣷⠸⣮⣿⣷⣨⣥⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⢁⡼⠃⣼⣿
⡟⠛⠛⠛⣿⠛⠛⢻⡟⠛⠛⢿⡟⠛⠛⡿⢻⡿⠛⡛⢻⣿⠛⡟⠛⠛⢿
⡇⢸⣿⠀⣿⠀⠛⢻⡇⠸⠃⢸⡇⠛⢛⡇⠘⠃⢼⣷⡀⠃⣰⡇⠸⠇⢸
⡇⢸⣿⠀⣿⠀⠛⢻⡇⢰⣿⣿⡇⠛⠛⣇⢸⣧⠈⣟⠃⣠⣿⡇⢰⣾⣿
⣿⣿⣿⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢋⣿⠙⣷⢸⣷⠀⣿⣿⣿
⣿⣿⣿⡇⢻⣿⣿⣿⡿⠿⢿⣿⣿⣿⠟⠋⣡⡈⠻⣇⢹⣿⣿⢠⣿⣿⣿
⣿⣿⣿⣿⠘⣿⣿⣿⣿⣯⣽⣉⣿⣟⣛⠷⠙⢿⣷⣌⠀⢿⡇⣼⣿⣿⣿
⣿⣿⣿⡿⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣤⡙⢿⢗⣀⣁⠈⢻⣿
*/
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
//Donald Trump pleese save this code
//Babahnineeleven will win IOI 2040
//Babahnineeleven will win IOI 2041
//Babahnineeleven will win IOI 2042
//Babahnineeleven will win IOI 2043
//Babahnineeleven will win IOI 2044
//Babahnineeleven will win IOI 2045
//Babahnineeleven will win IOI 2046
//Babahnineeleven will win IOI 2047
//Babahnineeleven will win IOI 2048
//Tanya Zadniprovska will win EGOI 2025
//Andrew Holod will NOT win IOI 2025
//Andrew Holod did not qualify to IOI 2025))))))))))
//Andrew Kholod will win ICPC WF 2026
//Andrew Pavlyk is best coder in Khmelnytski
//MoonSlay will NOT get Into IOI
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <bitset>
#include <stack>
#include <map>
#include <vector>
#include <set>
#include <algorithm>
#define endl '\n'
using namespace std;
FILE* stream;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
typedef pair < ld, ld > pdd;
const long long DIM = 500007;
const ld eps = 1e-12;
const long long INF = 3e18;
const long long Bsize = 450;
const int mod = 1e9 + 7;
const long long NUMSZ = 500;
/*
void rotate(vector < int > t, int x) {
cout << "Rotate: " << x << " ";
for (auto a : t) {
cout << a << " ";
}
cout << endl;
}
*/
void rotate(vector < int > t, int x);
void energy(int n, vector < int > v) {
int mxAng = 50000;
if (n == 2) {
rotate({ 0 }, ((mxAng / 2 + v[1] - v[0]) % mxAng + mxAng) % mxAng);
return;
}
vector < pii > a(n);
for (int i = 0; i < n; i++) a[i] = { v[i], i };
sort(a.begin(), a.end());
while((a[n - 1].first - a[0].first) % mxAng > mxAng / 2) {
rotate({ a[0].second }, mxAng / 2);
a[0].first = (a[0].first + (mxAng / 2)) % mxAng;
sort(a.begin(), a.end());
}
if ((a[n - 1].first - a[0].first) % mxAng < mxAng) {
if (a[n - 1].first - (mxAng / 2) >= 0) {
rotate({ a[0].second }, ((a[n - 1].first - (mxAng / 2) - a[0].first) % mxAng + mxAng) % mxAng);
a[0].first = ((a[n - 1].first - (mxAng / 2)) % mxAng + mxAng) % mxAng;
}
else {
rotate({ a[n - 1].second }, ((a[0].first + (mxAng / 2) - a[n - 1].first) % mxAng + mxAng) % mxAng);
a[n - 1].first = ((a[0].first + (mxAng / 2)) % mxAng + mxAng) % mxAng;
}
sort(a.begin(), a.end());
}
for (int i = 0; i < n / 2; i++) {
rotate({ a[i].second }, ((a[0].first - a[i].first) % mxAng + mxAng) % mxAng);
}
for (int i = n / 2; i < n; i++) {
rotate({ a[i].second }, ((a[n - 1].first - a[i].first) % mxAng + mxAng) % mxAng);
}
}
/*
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef _DEBUG
freopen_s(&stream, "input.txt", "r", stdin);
freopen_s(&stream, "output.txt", "w", stdout);
#endif
energy(3, { 5000, 12500, 37500 });
return 0;
}
*/
