#include "shoes.h"
#include <vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;
int sum(int a, int b, int m, vector<int>& tree) {
int ut = 0;
a += m; b += m;
while (a <= b) {
if (a%2 == 1) ut += tree[a++];
if (b%2 == 0) ut += tree[b--];
a /= 2; b /= 2;
}
return ut;
}
void add(int x, int k, int m, vector<int>& tree) {
k += m;
tree[k] += x;
for (k /= 2; k >= 1; k /= 2) {
tree[k] = tree[2*k] + tree[2*k+1];
}
}
long long count_swaps(std::vector<int> s) {
int tot = 0;
int n = s.size();
vector<pair<int,int>> par;
map<int, int> sett;
for (int i = 0; i < n; i++) {
if (sett.count(-s[i])) {
par.emplace_back(sett[-s[i]], i);
sett.erase(-s[i]);
}
else {
if (s[i] > 0) ++tot;
sett[s[i]] = i;
}
}
sort(par.begin(), par.end());
int x = ceil(log2(n));
int m = 1 << x;
vector<int> tree(2*m, 0);
for (int i = 0; i < n; i++) add(1, i, m, tree);
for (pair<int, int> p: par) {
tot += sum(p.first + 1, p.second - 1, m, tree);
add(-1, p.first, m, tree); add (-1, p.second, m, tree);
}
return tot;
}
