It’s easy to find the number of inversions. Now when we put the last number x in the front, We remove n-x and add x-1 inversions. This is easy to see because there are n-x numbers greater than x, so those are now in front of x, and were before x, therefore we lose n-x inversions. There were x-1 numbers less than x which were before x, and are now after x, therefore the number of inversions increases by x-1.

Also why would you use fenwick tree over pbds to find inversions. The latter takes 4 lines to code.

##
My solution

```
#include <iostream>
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define mp make_pair
#define pb push_back
using namespace std;
using namespace __gnu_pbds;
using ll = long long int;
using indexed_set = tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update>;
void solve(){
int n;
cin>>n;
vector<int> seq(n);
for(auto &x : seq){
cin>>x;
}
ll inv = 0;
indexed_set curr;
for(const auto &x : seq){
inv+=curr.size() - curr.order_of_key(x);
curr.insert(x);
}
ll ans = inv;
for(int i=n-1;i>0;--i){
inv-=n+1-2*seq[i];
ans^=inv;
}
cout<<ans<<"\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--){
solve();
}
}
```