#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
using ll = long long;
#define debug(v) \
cerr << "Line(" << __LINE__ << ") -> " << #v << " = " ;
#define dbx(x) debug(x); cerr << x << "\n";
#define dbg(x) debug(x); cerr << "{ "; for(auto &e : x) cerr << e << ", "; cerr << "} \n";
#define log(x) (31^__builtin_clz(x))
const int N = 1e6+10, MOD = 1e9+7;
template<typename T> struct BIT
{
int size = 0;
vector<T> tree;
BIT(int n): size(n), tree(n){}
// 1-indexed pos (0-index just add ++pos)
void add(int pos, ll val){
for(++pos ; pos <= size ; pos += (pos & (-pos))) tree[pos - 1] += val;
}
T get(int pos){
T res = 0;
for(++pos ; pos ; pos -= (pos & (-pos))) res += tree[pos - 1];
return res;
}
T query(int l, int r){
if(r < l) return 0;
return get(r) - get(l - 1);
}
};
ll count_swaps(vector<int> S){
int n = S.size();
vector<int> a = S;
BIT<int> bit(n+1);
queue<int> l[n+1], r[n+1];
for(int i = 0 ; i < n ; i ++){
if(a[i] < 0)l[-a[i]].push(i);
else r[a[i]].push(i);
}
ll ans = 0;
for(int i = 0 ; i < n ; i ++){
if(a[i] == 0)continue;
if(a[i] < 0)
{
int j = r[-a[i]].front();
r[-a[i]].pop();
l[-a[i]].pop();
a[j] = 0;
ans += bit.query(i, j) + j - i - 1;
bit.add(j, -1);
}
else
{
int j = l[a[i]].front();
l[a[i]].pop();
r[a[i]].pop();
a[j] = 0;
ans += bit.query(i, j) + j - i;
bit.add(j, -1);
}
}
return ans;
}
/*
*/
