#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct SegmentTree {
ll n = 1e5 + 1; vector<ll> st;
SegmentTree(): st(n * 4) {}
void update(ll id, ll l, ll r, ll pos, ll val) {
if (r < pos || l > pos) return;
if (l == r) {st[id] += val; return;}
ll mid = (l + r) >> 1;
update(id * 2, l, mid, pos, val);
update(id * 2 + 1, mid + 1, r, pos, val);
st[id] = st[id * 2] + st[id * 2 + 1];
}
void update(ll pos, ll val) {update(1, 0, 49999, pos, val);}
ll get(ll id, ll l, ll r, ll u, ll v) {
if (u > r || l > v) return 0;
if (u <= l && r <= v) return st[id];
ll mid = (l + r) >> 1;
return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
}
ll get(ll l, ll r) {
l = max(l, 0ll);
r = min(r, 49999ll);
if (l > r) return 0;
return get(1, 0, 49999, l, r);
}
};
ll n;
vector<int> v;
vector<int> pos;
vector<array<int, 2>> a;
SegmentTree st;
void rotate(vector<int> t, int x);
void prepare(int nn, vector<int> vv) {
n = nn; v = vv; pos.resize(n);
for (int i = 0; i < v.size(); i ++) a.push_back({v[i], i});
sort(a.begin(), a.end());
for (int i = 0; i < v.size(); i ++) v[i] = a[i][0], pos[i] = a[i][1];
}
void sub1() {
for (int i = 0; i < v.size() / 2; i ++)
rotate({pos[i]}, 100000 - v[i]);
for (int i = v.size() / 2; i < v.size(); i ++)
rotate({pos[i]}, 25000 - v[i]);
return;
}
ll cal(vector<int> v) {
ll res = 0;
for (int i = 0; i < (int)v.size(); i ++) {
for (int j = i + 1; j < (int)v.size(); j ++) {
int d = abs(v[i] - v[j]);
res += min(d, 50000 - d);
}
} return res;
}
bool check_x_y(ll x, ll y) {
if (x > 25000 && y < 25000) return 0;
if (x >= 25000 && y >= 25000) {
if (st.get(y - 25000 + 1, x - 25000 - 1) > 0) return 0;
ll I = st.get(x, 49999);
ll III = st.get(x - 25000, y);
ll V = st.get(0, y - 25000);
if (I + V - 1 < III) return 0;
return 1;
}
if (st.get(y + 25000 + 1, x + 25000 - 1) > 0) return 0;
ll I = st.get(x + 25000, 49999);
ll III = st.get(x, y + 25000);
ll V = st.get(0, y);
if (III - 1 < I + V) return 0;
return 1;
}
bool check_y_x(ll x, ll y) {
if (x < 25000 && y > 25000) return 0;
if (x >= 25000 && y >= 25000) {
if (st.get(x - 25000 + 1, y - 25000 - 1) > 0) return 0;
ll I = st.get(y, 49999);
ll III = st.get(y - 25000, x - 1);
ll V = st.get(0, x - 25000);
if (III < I + V) return 0;
return 1;
}
if (st.get(x + 25000 + 1, y + 25000 - 1) > 0) return 0;
ll I = st.get(y + 25000, 49999);
ll III = st.get(y, x + 25000);
ll V = st.get(0, x - 1);
if (I + V < III) return 0;
return 1;
}
void energy(int nn, vector<int> vv) {
prepare(nn, vv);
if (v.back() <= 25000) {sub1(); return;}
for (int i = n - 1; i >= 0; i --) v[i] -= v[0];
for (int i = 0; i < n; i ++) st.update(v[i], 1);
bool ok = false;
for (;;) {
if (v.back() <= 25000) break;
if (v[0] >= 24999) break;
if (v.back() - v[0] <= 25000) break;
if (ok) return; ok = true;
for (int i = 0; i < n; i ++) {
int start = 0;
if (i != 0) start = max(start, v[i - 1]);
for (int j = start; j <= v[i] - 1; j ++) {
if (!check_x_y(v[i], j)) continue;
rotate({pos[i]}, j - v[i] + 100000);
st.update(v[i], -1);
v[i] = j, ok = false;
st.update(v[i], 1);
j = start - 1;
}
}
for (int i = 0; i < n; i ++) {
int endpoint = 49999;
if (i != n - 1) endpoint = min(endpoint, v[i + 1]);
for (int j = endpoint; j >= v[i] + 1; j --) {
if (!check_y_x(v[i], j)) continue;
if (n >= 2000) {
for (int i = 1; i <= 1000; i ++)
rotate({pos[i]}, j - v[i] + 100000);
}
st.update(v[i], -1);
v[i] = j, ok = false;
st.update(v[i], 1);
j = endpoint + 1;
}
}
}
if (v.back() <= 25000) {
for (int i = 0; i < n / 2; i ++) rotate({pos[i]}, 0 - v[i] + 100000);
for (int i = n / 2; i < n; i ++) rotate({pos[i]}, 25000 - v[i] + 100000);
return;
}
if (v[0] >= 24999) {
for (int i = 0; i < n / 2; i ++) rotate({pos[i]}, 24999 - v[i] + 100000);
for (int i = n / 2; i < n; i ++) rotate({pos[i]}, 49999 - v[i] + 100000);
}
if (v.back() - v[0] >= 25000) {
ll x = v[0], y = v.back();
for (int i = 0; i < n / 2; i ++) rotate({pos[i]}, x - v[i] + 100000);
for (int i = n / 2; i < n; i ++) rotate({pos[i]}, y - v[i] + 100000);
}
}
