#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=2e5+5;
int n;
queue<int> lft[nx], rgt[nx];
ll res;
struct fenwick
{
int f[nx];
void update(int i, int vl) {while (i<=n) f[i]+=vl, i+=(i&-i);}
int query(int i)
{
int res=0;
while (i) res+=f[i], i-=(i&-i);
return res;
}
} f;
long long count_swaps(std::vector<int> s) {
n=s.size();
for (int i=1; i<=n; i++)
{
if (s[i-1]<0) lft[-s[i-1]].push(i);
else rgt[s[i-1]].push(i);
f.update(i, 1);
}
for (int i=1; i<=n; i++)
{
int shoe;
if (s[i-1]<0)
{
shoe=-s[i-1];
if (lft[shoe].empty()||lft[shoe].front()!=i) continue;
lft[shoe].pop();
int idxr=rgt[shoe].front();
rgt[shoe].pop();
f.update(idxr, -1);
res+=f.query(idxr-1)-f.query(i);
}
else
{
shoe=s[i-1];
if (rgt[shoe].empty()||rgt[shoe].front()!=i) continue;
rgt[shoe].pop();
int idxl=lft[shoe].front();
lft[shoe].pop();
f.update(idxl, -1);
res+=f.query(idxl-1)-f.query(i)+1;
}
// cout<<"debug "<<i<<' '<<res<<'\n';
}
return res;
}
