1896E - Permutation Sorting - CodeForces Solution

//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl        '\n'
#define F           first
#define S           second
#define pii         pair<int,int>
#define all(x)      x.begin(),x.end()
#define pb          push_back
#define fastio      ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll; 
typedef long double dll;

const int N = 2e6+7; 
int a[N], pos[N], ans[N], fen[N];
vector<pii> vec; 
int n;

void upd(int i){
     for(;i<=2*n; i+=(i&-i)) fen[i]++;
}

int get(int i){
     int ans = 0; 
     for(;i>0; i-=(i&-i)) ans += fen[i]; 
     return ans;
}

int32_t main(){
     fastio;

     int t; cin >> t;
     while(t--){
          cin >> n; 
          for(int i=1; i<=n; i++){
               cin >> a[i]; 
               pos[a[i]] = i; 
          }
          for(int i=n+1; i<=2*n; i++) a[i] = a[i-n]; 
          vec.clear();
          for(int i=1; i<=n; i++){
               if (pos[i] <= i){
                    vec.pb({pos[i],i});
                    vec.pb({pos[i]+n,i+n});
               }
               else vec.pb({pos[i],n+i});
          }
          for(int i=0; i<int(vec.size()); i++) swap(vec[i].F,vec[i].S);
          sort(all(vec)); 
          fill(fen,fen+2*n+1,0); 
          for(pii cur : vec){
               int l = cur.S, r = cur.F; 
               ans[a[l]] = r-l - (get(2*n) - get(l-1));
               upd(l); 
          }
          for(int i=1; i<=n; i++) cout << ans[i] << " ";
          cout << endl;
     }

     return 0;
}