For every cyclic shift, we basically erase the first number from the permutation and add it to the end of the permutation.

calculate the number of inversions in the permutation at the \(0th\) cyclic shift, You can calculate it with fenwick tree or segment tree or ordered set in C++.

For every \(i > 0\), let \(x\) be the number of inversions for the \(i-1\)th cyclic shift, now we need to update \(x\) to calculate the number of inversions at the \(ith\) cyclic shift, so we need to subtract from \(x\) the contribution of the first element in the permutation and then add its new contribution when it’s the last element of the permutation.

the old contribution of the first element to the number of inversions is The number of elements \(j\) such that \(a_j < a_0\), \(0 < j < n\) and since it’s a permutation so it’s equal to \(a_0\).

the new contribution of the first element to the number of inversions is The number of elements \(j\) such that \(a_j > a_0\), \(0 < j < n\) and since it’s a permutation so it’s equal to \(n-1-a_0\).

since at the \(ith\) cycle shift the \(ith\) element in the permutation becomes the first one so subtract \(a_i\) from x and add \(n-1-a_i\) to \(x\).

total complexity: \(O(NlogN)\)

implementation:

#include <bits/stdc++.h>

using namespace std ;

#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace __gnu_pbds;

template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update> ;

const int MAX = 3e5 + 10 ;

int arr[MAX] ;
int n ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 0 ; i < n ; ++i)
		cin>>arr[i] ;
	ordered_set<int>s ;
	long long ans = 0 ;
	for(int i = 0 ; i < n ; ++i)
	{
		ans += (s.size() - s.order_of_key(arr[i])) ;
		s.insert(arr[i]) ;
	}
	cout<<ans<<"\n" ;
	for(int i = 0 ; i < n-1 ; ++i)
	{
		ans -= arr[i] ;
		ans += n - 1 - arr[i] ;
		cout<<ans<<"\n" ;
	}
	return 0 ;
}