#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
unordered_map<int, vector<int>> ap;
const int NMAX=2e5;
struct Fenwick
{
int a[NMAX+11];
Fenwick()
{
for(auto &x:a)x=0;
}
void update(int poz, int val)
{
for(; poz<=NMAX+10; poz+=poz&(-poz))
a[poz]+=val;
}
int query(int poz)
{
int suma=0;
for(; poz>0; poz-=poz&(-poz))
suma+=a[poz];
return suma;
}
}aib;
long long count_swaps(vector<int> S)
{
int n=S.size();
int v[n+1];
bool folosit[n+1];
for(auto &x:folosit)x=false;
for(int i=0; i<n; i++)
{
v[i+1]=S[i];
ap[v[i+1]].push_back(i+1);
}
for(auto [x, y]:ap)
reverse(ap[x].begin(), ap[x].end());///ca se le iau cu pop back
long long ans=0;
for(int i=1; i<=n; i++)
{
if(!folosit[i])
{
int nxt = ap[-v[i]].back();
ap[-v[i]].pop_back();
folosit[nxt]=true;
ans+=(nxt+aib.query(nxt))-(i+aib.query(i))-1;
if(v[i]>0)ans++;
aib.update(i, 1);
aib.update(nxt, -1);
ap[v[i]].pop_back();
}
}
return ans;
}
