#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
class FenwickTree{
vector<int> bit; int N;
public:
FenwickTree(int n) : N(n){bit.resize(N+1);};
void update(int i, int x){
for(; i<=N; i+=(i&(-i))) bit[i] += x;
}
int query(int i){
int res = 0;
for(; i>0; i-=(i&(-i))) res += bit[i];
return res;
}
int query(int l, int r){
return query(r) - query(l-1);
}
};
const int MAXN = 1e5;
queue<int> _pos[2*(MAXN + 1)];
queue<int> *pos = _pos + (MAXN + 1);
#define left_shoe(x) 2*x + 1
#define right_shoe(x) 2*x + 2
long long count_swaps(vector<int> s) {
int N = s.size();
FenwickTree ft(N << 1);
long long cnt_swaps = 0;
for(int i=0; i<N; i++){
if(pos[-s[i]].empty()){
pos[s[i]].push(i);
ft.update(left_shoe(i), 1);
}
else{
int j = pos[-s[i]].front();
pos[-s[i]].pop();
int k = ft.query(right_shoe(j), left_shoe(i));
if(s[i] < 0) k++;
cnt_swaps += k;
ft.update(right_shoe(j), 1);
}
}
return cnt_swaps;
}
