#include "rotate.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define tiii tuple<int,int,int>
#define tiiii tuple<int,int,int,int>
#define pb push_back
#define eb emplace_back
#define emp emplace
#define mkp make_pair
#define mkt make_tuple
#define vctr vector
#define arr array
#define all(x) x.begin(), x.end()
#define amin(a,b) a = min(a,b)
#define amax(a,b) a = max(a,b)
#define brick(x) cout << #x << " = " << (x) << " | "
#define dbg(x) cout << #x << " = " << (x) << '\n'
#define vdbg(a) cout << #a << " = "; for(auto _x : a)cout << _x << ' '; cout << '\n'
#define adbg(a,n) cout << #a << " = "; for(int _i = 1; _i <= n; ++_i)cout << a[_i] << ' '; cout << '\n'
#define adbg0(a,n) cout << #a << " = "; for(int _i = 0; _i < n; ++_i)cout << a[_i] << ' '; cout << '\n'
mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));
int uid(int a, int b) { return uniform_int_distribution<int>(a,b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a,b)(rng); }
const int MOD = 1e9+7; // 998244353;
struct FenwickTree {
using T = int;
T tree[50005];
int n = -1;
void init(int _n) {
n = _n;
fill(tree+1,tree+n+1,0);
}
void upd(int x, T val) {
++x;
assert(n > 0);
for (int i = x; i <= n; i += i&-i) {
tree[i] += val;
}
return;
}
T qry(int y) {
assert(n > 0);
T res = 0;
for (int i = y; i > 0; i -= i&-i) {
res += tree[i];
}
return res;
}
T qry(int x, int y) {
assert(n > 0);
++x;
++y;
return qry(y)-qry(x-1);
}
} tree;
int a[100005];
vctr<int> b[50005];
void energy(int n, vctr<int> va) {
tree.init(50000);
multiset<int> st;
for (int i = 1; i <= n; ++i) {
a[i] = va[i-1];
b[a[i]].pb(i);
tree.upd(a[i],1);
st.insert(a[i]);
}
auto f = [&](int l, int r) -> tiii {
int sum = tree.qry(l,r);
auto it = st.upper_bound(r);
int mx = -1;
if (it != st.begin() && l <= *prev(it))mx = *prev(it);
int mn = -1;
auto it2 = st.lower_bound(l);
if (it2 != st.end() && *it2 <= r)mn = *it2;
return mkt(sum,mn,mx);
};
auto g = [&](int l, int r) -> tiii {
l = (l+50000)%50000;
r = (r+50000)%50000;
if (l <= r) {
return f(l,r);
}
tiii y = f(l,49999);
tiii x = f(0,r);
tiii res;
get<0>(res) = get<0>(x)+get<0>(y);
get<1>(res) = get<1>(y);
if (get<1>(res) == -1)get<1>(res) = get<1>(x);
get<2>(res) = get<2>(x);
if (get<2>(res) == -1)get<2>(res) = get<2>(y);
return res;
};
for (int j = 0; j < 50000; ++j) {
while (b[j].size()) {
if (n == 1)break;
int p = b[j].back();
b[j].pop_back();
if (b[(j+25000)%50000].size()) {
int q = b[(j+25000)%50000].back();
b[(j+25000)%50000].pop_back();
tree.upd(j,-1);
tree.upd((j+25000)%50000,-1);
st.erase(st.find(j));
st.erase(st.find((j+25000)%50000));
n -= 2;
continue;
}
tiii resl, resr;
resl = g(j-25000,j);
resr = g(j,j+25000);
int z;
if (get<0>(resl) >= get<0>(resr)) {
z = get<1>(resl);
} else {
z = get<2>(resr);
}
rotate({p-1},z+25000-j);
int q = b[z].back();
b[z].pop_back();
tree.upd(j,-1);
tree.upd(z,-1);
st.erase(st.find(j));
st.erase(st.find(z));
n -= 2;
}
}
return;
}
