#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); } }