#include "rotate.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define speedIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//#define mod 1000000007
#define f first
#define s second
#define pii pair<long long,long long>
#define pb push_back
const long long M=50000;
vector<int> final,bit;
long long total_cost, last_energy;
bool flag=false;
long long get(long long n, long long i){
i++;
long long ans=0;
while(i>0){
ans+=bit[i];
i-=i&(-i);
}
return ans;
}
void update(long long n, long long i, long long x){
i++;
while(i<=n){
bit[i]+=x;
i+=i&(-i);
}
}
/*void rotate(vector<long long> t, long long x){
cout<<"rotate ";
for(long long i:t){
cout<<i<<' ';
final[i]=(final[i]+x)%M;
}
cout<<"by "<<x<<'\n';
}*/
void energy(int nn, vector<int> vv){
long long n=nn;
vector<pii> w(n);
for(long long i=0;i<n;i++){
w[i]={vv[i],i};
}
sort(w.begin(),w.end());
set<pair<pii,long long>> a;
for(long long i=0;i<n;i++){
a.insert({{w[i].f,i},w[i].s});
}
//will work with w, w[i].s is the og index.
// a.f.f is value, a.f.s is the sorted index and a.s is the og index.
long long idx=0;
vector<long long> marked(n,0);
bit.resize(n+1,0);
for(long long i=1;i<=n;i++){
bit[i]=i&(-i);
}
while(idx<n){
//cout<<a.size()<<'\n';
if(marked[idx]){
idx++;
continue;
}
marked[idx]=1;
update(n,idx,-1);
if(w[idx].f<M/2){
auto it=a.upper_bound({{w[idx].f+M/2,1e9},1e9});
it--; // j st w[j]<=w[i]+M/2<w[j+1]
auto element=*it;
if(get(n,element.f.s)-get(n,idx)>=a.size()/2){
rotate({w[idx].s},w[element.f.s].f+M/2-w[idx].f);
a.erase({{w[idx].f,idx},w[idx].s});
w[idx].f=(w[element.f.s].f+M/2)%M;
//a.insert({{w[idx].f,idx},w[idx].s});
update(n,element.f.s,marked[element.f.s]-1);
marked[element.f.s]=1;
a.erase({{w[element.f.s].f,element.f.s},w[element.f.s].s});
}else{
rotate({w[idx].s},w[(element.f.s+1)%n].f+M/2-w[idx].f);
a.erase({{w[idx].f,idx},w[idx].s});
w[idx].f=(w[(element.f.s+1)%n].f+M/2)%M;
//a.insert({{w[idx].f,idx},w[idx].s});
update(n,(element.f.s+1)%n,marked[(element.f.s+1)%n]-1);
marked[(element.f.s+1)%n]=1;
a.erase({{w[(element.f.s+1)%n].f,(element.f.s+1)%n},w[(element.f.s+1)%n].s});
}
}else{
auto it=a.lower_bound({{w[idx].f-M/2,0},0});
//it--; // j st w[j-1]<w[i]+M/2<=w[j]
auto element=*it;
if(get(n,idx)-get(n,element.f.s)>=a.size()/2){
rotate({w[idx].s},w[element.f.s].f+M/2-w[idx].f);
a.erase({{w[idx].f,idx},w[idx].s});
w[idx].f=(w[element.f.s].f+M/2)%M;
//a.insert({{w[idx].f,idx},w[idx].s});
update(n,element.f.s,marked[element.f.s]-1);
marked[element.f.s]=1;
a.erase({{w[element.f.s].f,element.f.s},w[element.f.s].s});
//cout<<idx<<" pairs with "<<element.f.s<<'\n';
}else{
long long lmao=(element.f.s-1)%n;
if(lmao<0) lmao+=n;
rotate({w[idx].s},w[lmao].f+M/2-w[idx].f);
a.erase({{w[idx].f,idx},w[idx].s});
//cout<<lmao<<" lmao\n";
w[idx].f=(w[lmao].f+M/2)%M;
//a.insert({{w[idx].f,idx},w[idx].s});
update(n,lmao,marked[lmao]-1);
marked[lmao]=1;
a.erase({{w[lmao].f,lmao},w[lmao].s});
//cout<<idx<<" pairs with "<<lmao<<'\n';
}
}
idx++;
}
}
