#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct BIT {
int n;
vector<int> e;
BIT(int b) {
b++;
e.resize(b);
n=b;
}
void upd(int at, int val) {
at++;
while(at<n) {
e[at]+=val;
at+=at&(-at);
}
}
int que(int at) {
int sum=0;
at++;
while(at >0) {
sum+=e[at];
at-=at&(-at);
}
return sum;
}
};
long long count_swaps(std::vector<int> s) {
int n= s.size();
int ans=0;
BIT b(n);
for(int i = 0;i<n;i++)b.upd(i, 1);
map<int, vector<int>> mp;
for(int i = n-1;i>=0;i--) {
mp[s[i]].push_back(i);
}
for(int i = 0;i<n;i++) {
if(s[i] == 0)continue;
int at = mp[-s[i]].back();
// cout << i << " " << b.que(i) << " " << b.que(at) << " " << s[i] << endl;
ans+=b.que(at)-b.que(i)-1;
b.upd(at, -1);
b.upd(i, -1);
mp[-s[i]].pop_back();
mp[s[i]].pop_back();
if(s[i] > 0)ans++;
s[i]=0;
s[at]=0;
}
return ans;
}
