#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class SegmentTree{
public:
int length = 1;
vector<ll> st;
void setup(vector<int>& values){
int N = values.size();
while(length < N) length *= 2;
st.resize(2 * length);
}
void update(int l, int r, int tl, int tr, int k){
if(tl > r || tr < l) return;
if(tl >= l && tr <= r){
st[k] += 1;
return;
}
int mid = (tl + tr) / 2;
update(l, r, tl, mid, k * 2);
update(l, r, mid + 1, tr, k * 2 + 1);
}
ll query(int index){
index += length;
ll sum = st[index];
for(int i = index / 2; i > 0; i /= 2){
sum += st[i];
}
return sum;
}
};
long long count_swaps(vector<int> s) {
int N = s.size();
map<int, set<int>> remain;
map<int, int> counter;
for(int i = 0; i < N; i++){
remain[s[i]].insert(i);
}
SegmentTree tree;
tree.setup(s);
ll sum = 0;
for(int i = 0; i < N; i++)
{
if(s[i] < 0 && counter[abs(s[i])] > 0 || s[i] > 0 && counter[abs(s[i])] < 0){
int inc = s[i] > 0 ? 1 : -1;
counter[abs(s[i])] += inc;
continue;
}
int inc = s[i] > 0 ? 1 : -1;
counter[abs(s[i])] += inc;
int turn = *(remain[s[i]].begin());
int other = *(remain[-1 * s[i]].begin());
int additional = s[turn] > s[other] ? 1 : 0;
int offset = abs(tree.query(turn) - tree.query(other));
int diff = abs(turn - other) - 1;
tree.update(turn, other, 0, tree.length - 1, 1);
// Remove pair
remain[s[i]].erase(remain[s[i]].begin());
remain[-1 * s[i]].erase(remain[-1 * s[i]].begin());
sum += additional - offset + diff;
}
return sum;
}
// #include "grader.cpp"
