#include "shoes.h"
#include <vector>
#include <deque>
#include <algorithm>
#include <map>
#define int long long int
using namespace std;
inline int Abs(int x){
return x > 0 ? x : -x;
}
const int maxN = 220226;
map<int, deque<int> > poss;
int bit[maxN], visited[maxN], id[maxN];
void modify(int p){
for(; p < maxN; p += (p & -p)) bit[p]++;
}
int query(int p){
int r = 0;
for(; p; p -= (p & -p)) r += bit[p];
return r;
}
int count_swaps(std::vector<signed> s) {
int N = s.size();
int t, cnt = 0;
for(int i = 0; i < N; i++){
visited[i] = false;
poss[s[i]].push_back(i);
}
/*
for(auto [id, p] : poss){
cout << id << ": ";
for(int x : p) cout << x << " ";
cout << endl;
}
*/
for(int i = 0; i < N; i++){
//cout << "D" << endl;
if(visited[i]) continue;
t = Abs(s[i]);
id[poss[-t].front()] = cnt++;
id[poss[t].front()] = cnt++;
visited[poss[t].front()] = true;
visited[poss[-t].front()] = true;
poss[t].pop_front();
poss[-t].pop_front();
}
//for(int i = 0; i < N; i++) cout << id[i] << " ";
//cout << endl;
int ans = 0;
for(int i = 0; i < N; i++){
ans += query(id[i] + 1);
modify(id[i] + 2);
}
return N * (N - 1) / 2 - ans;
}
