#include "shoes.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) for(auto sdg:v)cout<<sdg<<" ";cout<<"\n"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
vector<ll>a,p,pos; // permutation, position of idx
void move(ll i, ll j){ //move i to pos j by swapping j<i
//cout<<"move "<<i<<" "<<j<<"\n";
while(j<pos[i]){
ll &ant=p[pos[i]-1];
swap(pos[ant],pos[i]);
swap(ant,p[i]);
}
}
long long count_swaps(vector<int> S){
for(auto i:S)a.pb(i);
ll n=SZ(a)/2;
fore(i,0,2*n)p.pb(i),pos.pb(i);
vector<ll> l[n+1],r[n+1];
ll res=0;
fore(i,0,2*n){
ll s=abs(a[i]);
//cout<<i<<" "<<a[i]<<": "<<s<<"\n";
//imp(p); imp(pos);
if(a[i]<0){
//cout<<"l\n";
//imp(r[s]);
if(!SZ(r[s]))l[s].pb(i);
else {
ll j=r[s].back(); r[s].pop_back();
res+=i-pos[j];
move(i,pos[j]);
}
}
else {
//cout<<"r\n";
//imp(l[s]);
if(!SZ(l[s]))r[s].pb(i);
else {
ll j=l[s].back(); l[s].pop_back();
res+=i-(pos[j]+1);
move(i,pos[j]+1);
}
}
/*fore(i,0,n+1){
cout<<"l["<<i<<"]: "; imp(l[i]);
cout<<"r["<<i<<"]: "; imp(r[i]);
}*/
}
return res;
}
