#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T> using matrix = vector<vector<T>>;
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
template<typename T>
struct smartvec{
vector<T> v;
int n;
smartvec(int sz = 0){
n = sz;
v = vector<T>(2*sz+1);
}
T& operator[](int id){
return v[id+n];
}
};
long long count_swaps(std::vector<int> v) {
int n = v.size();
ll resp = 0;
vector<int> bit(n+1);
auto update=[&](int id, int val){
id++;
while(id<=n){
bit[id]+=val;
id+=id&-id;
}
};
auto query =[&](int id){
id++;
int ret = 0;
while(id){
ret+=bit[id];
id-=id&-id;
}
return ret;
};
smartvec<vector<int>> ocur(n);
for(int i = n-1; i >= 0; i--){
update(i,1);
ocur[v[i]].push_back(i);
}
vector<int> passed(n);
for(int i = 0; i < n; i++){
if(passed[i])
continue;
ocur[v[i]].pop_back();
update(i,-1);
int next = ocur[v[i]*-1].back();
ocur[v[i]*-1].pop_back();
update(next,-1);
passed[i] = 1;
passed[next] = 1;
resp+=query(next);
resp+=v[i]> 0;
}
return resp;
}
