//MRasool kheyri
//Iran -> Khorasan -> Ferdown -> Baghestan
//17/2/1405
//vasate azmoonima...
#include<bits/stdc++.h>
#include "rotate.h"
using namespace std ;
typedef long long ll ;
#define el '\n'
const ll maxn = 2e6 + 100 ;
const ll x = 50000 ;
ll mark[maxn] ;
vector<int> vec[maxn] ;
void energy(int n , vector<int> v){
for(ll i = 0 ; i < n ; i++){
vec[v[i]].push_back(i) ;
}
ll ok = 1 ;
while(ok){
ok = 0 ;
for(ll i = 0 ; i < x ; i++){
if(!vec[i].size()){continue;}
ll cnt1 = 0 , cnt2 = 0 ;
for(ll k = (i+x-1)%x ; k != (i+x/2)%x ; k = (k-1+x)%x){
cnt1 += vec[k].size() ;
}
for(ll k = (i+1)%x ; k != (i+x/2)%x ; k = (k+1)%x){
cnt2 += vec[k].size() ;
}
if(cnt1 < cnt2){
rotate(vec[i],x-1) ;
while(vec[i].size()){
ll A = vec[i].back() ;
vec[i].pop_back() ;
vec[(i+x-1)%x].push_back(A) ;
}
ok = 1 ;
break ;
}
else if(cnt1 > cnt2){
rotate(vec[i],1) ;
while(vec[i].size()){
ll A = vec[i].back() ;
vec[i].pop_back() ;
vec[(i+1)%x].push_back(A) ;
}
}
}
}
return ;
}
