#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
const ll N = 1 << 20;
ll n;
ll lazy[N];
ll seg[N];
void build(ll p = 1, ll l = 0, ll r = n-1) {
if (l > r) return;
if (l == r) {
seg[p] = l;
return;
}
ll mid = (l+r)/2;
build(p*2, l, mid);
build(p*2+1, mid+1, r);
seg[p] = min(seg[p*2], seg[p*2+1]);
}
void pushDown(ll p) {
for (ll h : {p*2, p*2+1}) {
lazy[h] += lazy[p];
seg[h] += lazy[p];
}
lazy[p] = 0;
}
void update(ll a, ll p = 1, ll l = 0, ll r = n-1) {
if (l > r || r < a) return;
if (a <= l) {
lazy[p]--;
seg[p]--;
return;
}
if (lazy[p] != 0) pushDown(p);
ll mid = (l+r)/2;
update(a, p*2, l, mid);
update(a, p*2+1, mid+1, r);
seg[p] = min(seg[p*2], seg[p*2+1]);
}
ll query(ll idx, ll p = 1, ll l = 0, ll r = n-1) {
if (l > r || idx < l || idx > r) return 0;
if (l == r) {
if (l == idx) return seg[p];
return 0;
}
if (lazy[p] != 0) pushDown(p);
ll mid = (l+r)/2;
ll a = query(idx, p*2, l, mid);
ll b = query(idx, p*2+1, mid+1, r);
return a+b;
}
long long count_swaps(std::vector<int> s) {
ll swaps = 0;
n = s.size();
build();
map<ll, ll> last; // ultima aparicion de zapatilla con sz x
vi next(n, -1); // idx de la pareja mas cercana de la zapatilla i
vi nextSame(n, -1); // idx de la zapatilla mas cercana de la misma sz
for (ll i = n-1; i >= 0; i--) {
if (last.count(-s[i])) next[i] = last[-s[i]];
if (last.count(s[i])) nextSame[i] = last[s[i]];
last[s[i]] = i;
}
vi vis(n, 0);
map<ll, ll> newNext; // nueva pareja mas cercana para zapatilla de sz x
map<ll, ll> newNextSame; // nueva zapatilla igual mas cercana para zapatilla de sz x
for (ll 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 (newNextSame.count(s[i])) {
if (newNextSame[s[i]] < nextSame[i]) {
newNextSame.erase(s[i]);
}
else {
nextSame[i] = newNextSame[s[i]];
}
}
// buscar zapatilla derecha de sz abs(s[i]) mas cercana
// y ponerla a la derecha
ll idx = next[i];
swaps += query(idx) - query(i) - 1;
if (newNextSame.count(-s[i])) {
if (newNextSame[-s[i]] > nextSame[idx]) {
nextSame[idx] = newNextSame[-s[i]];
}
}
ll nx = nextSame[idx];
if (newNext.count(s[i])) newNext[s[i]] = max(newNext[s[i]], nx);
else newNext[s[i]] = nx;
if (newNextSame.count(-s[i])) newNextSame[-s[i]] = max(newNextSame[-s[i]], nx);
else newNextSame[-s[i]] = nx;
vis[idx] = 1;
update(idx+1);
if (s[i] > 0) swaps++;
}
return swaps;
}
