#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>st;
void build(int i, int j, int p) {
if(i == j) {
st[p] = 1;
return;
}
int mid = (i+j)/2;
build(i,mid,2*p);
build(mid+1,j,2*p+1);
st[p] = st[2*p] + st[2*p+1];
}
int l,r;
int query(int i, int j, int p) {
if(i > r || j < l)
return 0;
if(i >= l && j <= r)
return st[p];
int mid = (i+j)/2;
return query(i,mid,2*p) + query(mid+1,j,2*p+1);
}
void update(int i, int j, int p) {
if(i > l || j < l)
return;
if(i == j) {
assert(i == l);
st[p]--;
return;
}
int mid = (i+j)/2;
update(i,mid,2*p);
update(mid+1, j, 2*p+1);
st[p] = st[2*p] + st[2*p+1];
}
long long count_swaps(vector<int>s) {
const int n = (int)s.size();
st.resize(8*n);
vector<queue<int>>po(n+1);
vector<queue<int>>ne(n+1);
for(int i = 0 ; i < n ; i++) {
if(s[i] > 0)
po[s[i]].push(i);
else
ne[-s[i]].push(i);
}
build(0,n-1,1);
int64_t ans = 0;
for(int i = 0 ; i < n ; i++) {
if(s[i] > 0) {
if(po[s[i]].front() != i) continue;
l = i, r = ne[s[i]].front();
ans += query(0,n-1,1) - 2;
l = r;
update(0,n-1,1);
ne[s[i]].pop();
po[s[i]].pop();
ans++;
} else {
if(ne[-s[i]].front() != i) continue;
l = i, r = po[-s[i]].front();
ans += query(0,n-1,1) - 2;
l = r;
update(0,n-1,1);
po[-s[i]].pop();
ne[-s[i]].pop();
}
}
return ans;
}
