#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
#define par pair<int,int>
#define f first
#define s second
#define ld long duble
#define ull unsigned long long
#define st short int
using namespace std;
int abi[1000006],N;
void add(int k){
while(k<=N) abi[k]++,k+=k&-k;
}
ll query(int k){
ll s=0;
while(k) s+=abi[k],k-=k&-k;
return s;
}
long long count_swaps(std::vector<int> vec) {
int n=vec.size();
vector <vector<int>> asd(n+1);
int arr[n+1],a;
for(int i=n-1;i>=0;i--) a=vec[i]+n/2,asd[a].push_back(i),arr[a]=asd[a].size()-1;
N=n;
ll solve=0;
fill(abi,abi+n,0);
bool vis[n];
fill(vis,vis+n,false);
for(int i=0;i<n;i++){
if(vis[i]) continue;
a=n/2-vec[i];
while(arr[a]>=0 && asd[a][arr[a]]<i) arr[a]--;
solve+=asd[a][arr[a]]-i-query(asd[a][arr[a]])+query(i);
if(a>n/2) solve--;
vis[asd[a][arr[a]]]=true;
add(asd[a][arr[a]--]);
}
return solve;
}
