#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define ll long long
long long count_swaps(std::vector<int> s) {
ll swaps = 0;
int n = s.size();
map<int, int> last; // ultima aparicion de zapatilla con sz x
vi next(n); // idx de la pareja mas cercana de la zapatilla i
vi nextSame(n); // idx de la zapatilla mas cercana de la misma sz
for (int i = n-1; i >= 0; i--) {
last[s[i]] = i;
next[i] = last[-s[i]];
nextSame[i] = last[s[i]];
//next[i] = (last.count(-s[i]) ? last[-s[i]] : -1);
}
vi vis(n, 0);
map<int, int> newNext; // nueva pareja mas cercana para zapatilla de sz x
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
if (newNext.count(s[i])) {
if (newNext[s[i]] < next[i]) {
newNext.erase(s[i]);
}
else {
next[i] = newNext[s[i]];
}
}
if (s[i] < 0) {
// buscar zapatilla derecha de sz abs(s[i]) mas cercana
// y ponerla a la derecha
int idx = next[i];
swaps += idx - i - 1;
newNext[s[i]] = nextSame[idx];
vis[idx] = 1;
}
else {
// buscar zapatilla izquierda de sz abs(s[i]) mas cercana
// y ponerla a la izquierda
int idx = next[i];
swaps += idx - i;
newNext[s[i]] = nextSame[idx];
vis[idx] = 1;
}
}
return swaps;
}
