#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct grup{
int x, y;
bool operator < (const grup &aux)const{
if((x + y) / 2 != (aux.x + aux.y) / 2) return (x + y) / 2 < (aux.x + aux.y) / 2;
return x < aux.x;
}
};
grup a[100005];
set <int> lf[200005], rf[200005];
int n;
int Arb[800005], Lazy[800005];
void propag(int nod){
for(int i = nod * 2; i <= nod * 2 + 1 ; ++i){
Lazy[i] += Lazy[nod];
Arb[i] += Lazy[nod];
}
Lazy[nod] = 0;
}
void build(int st = 1, int dr = n, int nod = 1){
Lazy[nod] = 0;
if(st == dr){
Arb[nod] = st;
return ;
}
int mij = (st + dr) / 2;
build(st, mij, nod * 2);
build(mij + 1, dr, nod * 2 + 1);
}
void update(int x, int y, int val, int st = 1, int dr = n, int nod = 1){
if(x <= st && dr <= y){
Lazy[nod] += val;
Arb[nod] += val;
return ;
}
propag(nod);
int mij = (st + dr) / 2;
if(x <= mij) update(x, y, val, st, mij, nod * 2);
if(mij + 1 <= y) update(x, y, val, mij + 1, dr, nod * 2 + 1);
}
int query(int x, int st = 1, int dr = n, int nod = 1){
if(st == dr) return Arb[nod];
propag(nod);
int mij = (st + dr) / 2;
if(x <= mij) return query(x, st, mij, nod * 2);
else return query(x, mij + 1, dr, nod * 2 + 1);
}
long long count_swaps(vector<int> s) {
int NR = 0;
n = s.size();
long long Sol = 0;
for(int i = 1; i <= n ; ++i){
int x = s[i - 1];
if(x < 0){
x = -x;
if(!rf[x].empty()){
a[++NR] = {i, *rf[x].begin()};
rf[x].erase(rf[x].begin());
//++Sol;
}
else lf[x].insert(i);
}
else{
if(!lf[x].empty()){
a[++NR] = {*lf[x].begin(), i};
lf[x].erase(lf[x].begin());
}
else rf[x].insert(i);
}
}
sort(a + 1, a + NR + 1);
//cerr << n;
build();
for(int i = 1; i <= NR ; ++i){
int p1 = 2 * i - 1, p2 = 2 * i;
int x = query(a[i].x);
Sol = Sol + abs(x - p1);
update(1, a[i].x, 1);
int y = query(a[i].y);
Sol = Sol + abs(y - p2);
update(1, a[i].y, 1);
}
return Sol;
}
