#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 + 1, 49999); ll III = st.get(x - 25000, y); ll V = st.get(0, y - 25000); // cout << "X, Y: " << x << ' ' << y << endl; // cout << "I III V: " << I << ' ' << III << ' ' << V << endl; if (I + V < 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 + 1, y + 25000); ll V = st.get(0, y); if (III < 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;} { vector<int> v; for (int i = 0; i < n; i ++) v.push_back(i); rotate(v, 0 - v[0] + 100000); for (int i = n - 1; i >= 0; i --) ::v[i] -= ::v[0]; for (int i = 0; i < n; i ++) st.update(::v[i], 1); } ll old_value = cal(v); bool ok = false; for (;;) { if (v.back() <= 25000) break; if (ok) return; ok = true; // for (auto x: v) cout << x << ' '; cout << endl; for (int i = 0; i < n; i ++) { vector<int> cur = v; int start = 0; if (i != 0) start = max(start, v[i - 1]); for (int j = start; j <= v[i] - 1; j ++) { cur[i] = j; if (!check_x_y(v[i], j)) {cur[i] = v[i]; 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; } } for (int i = 0; i < n; i ++) { vector<int> cur = v; int endpoint = 49999; if (i != n - 1) endpoint = min(endpoint, v[i + 1]); for (int j = endpoint; j >= v[i] + 1; j --) { cur[i] = j; if (!check_y_x(v[i], j)) {cur[i] = v[i]; continue;} // cout << v[i] << ' ' << j << ' ' << cal(cur) << ' ' << cal(v) << endl;; rotate({pos[i]}, j - v[i] + 100000); st.update(v[i], -1); v[i] = j, ok = false; st.update(v[i], 1); j = endpoint; } } } 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); }