#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) { v.clear(); pos.clear(); a.clear(); st.st.assign(4 * (1e5 + 1), 0); prepare(nn, vv); if (v.back() <= 25000) {sub1(); return;} { vector<int> v; for (int i = 0; i < n; i ++) v.push_back(i); for (int i = 1; i <= 20; 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); } }