#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
void updateSegTree(vector<int> &segtree, int p, int a){
int N = segtree.size() / 2;
p += N;
segtree[p] = a;
p /= 2;
while (p > 0){
segtree[p] = segtree[2 * p] + segtree[2 * p + 1];
p /= 2;
}
}
long long querySegTree(vector<int> &segtree, int l, int r){
int N = segtree.size() / 2;
long long total = 0;
for (l += N, r += N; l < r; l /= 2, r /= 2){
if (l % 2 == 1){
total += segtree[l++];
}
if (r % 2 == 1){
total += segtree[--r];
}
}
return total;
}
long long count_swaps(vector<int> s) {
int N = s.size();
long long total = 0;
vector<int> segtree(2 * N, 0);
for (int i = 0; i < N; i++){
updateSegTree(segtree, i, 1);
}
vector<set<int> > positions (2 * N + 1, set<int> ());
for (int i = 0; i < N; i++){
positions[s[i] + N].insert(i);
}
for (int i = 0; i < N; i++){
int current_value = querySegTree(segtree, i, i + 1);
if (current_value == 1){
int current_shoe = s[i];
int desired_shoe = -current_shoe;
int desired_shoe_location = *(positions[N + desired_shoe].begin());
positions[N + desired_shoe].erase(positions[N + desired_shoe].begin());
positions[N + current_shoe].erase(positions[N + current_shoe].begin());
updateSegTree(segtree, i, 0);
updateSegTree(segtree, desired_shoe_location, 0);
if (desired_shoe < 0){
total++;
}
total += querySegTree(segtree, i, desired_shoe_location);
}
}
return total;
}
