#include "shoes.h"
#include <iostream>
#include <vector>
#include <deque>
#include <cmath>
#include <bit>
#include <unordered_map>
using namespace std;
void inline update(vector<int>& removed, int pos) {
while (pos > 0) {
removed[pos]++;
pos >>= 1;
}
}
int inline sum(vector<int>& removed, int i, int j) {
int res = 0;
while (i >> 1 < j >> 1) {
if ((i % 2) == 0)
res += removed[i+1];
if ((j % 2) == 1)
res += removed[j-1];
i >>= 1;
j >>= 1;
}
return res;
}
int inline pwr(int x) {
int res = 1;
while (res < x) {
res <<= 1;
}
return res;
}
long long count_swaps(std::vector<int> S) {
long long res = 0;
unordered_map<int, deque<int>> sizes[2];
int N = pwr(S.size());
vector<int> removed(2*N, 0);
for (int i=0; i<S.size(); i++)
S[i] < 0 ? sizes[0][-S[i]].push_back(i) : sizes[1][S[i]].push_back(i);
for (int i=0; i<S.size(); i++) {
if (sizes[0][abs(S[i])].empty() || sizes[S[i] > 0][abs(S[i])].front() > i)
continue;
int j = sizes[(S[i] < 0)][abs(S[i])].front();
sizes[0][abs(S[i])].pop_front();
sizes[1][abs(S[i])].pop_front();
res += j - i - sum(removed, N+i, N+j);
update(removed, N+j);
if (S[i] < 0) res--;
}
return res;
}
