#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
struct node
{
int octopus, l, r;
node *lkid, *rkid;
node(int a, int b){l = a, r = b, octopus = r-l+1;}
node(){}
};
node *rt;
void build(node *cur)
{
//cout<<cur->l<<cur->r<<cur->octopus;
if(cur->l == cur->r)
{
cur->octopus = 1;
return;
}
int mid = (cur->l+cur->r)/2;
cur -> lkid = new node(cur->l, mid);
cur -> rkid = new node(mid+1, cur->r);
build(cur->lkid);
build(cur->rkid);
return;
}
int query(node *cur, int ql, int qr)
{
if(cur -> r < ql || cur -> l > qr)
return 0;
if(cur -> r <= qr && cur -> l >= ql)
return cur->octopus;
return query(cur -> lkid, ql, qr) + query(cur -> rkid, ql, qr);
}
void update(node *cur, int ind)
{
if(cur->l > ind || cur->r < ind)
return;
cur->octopus--;
if(cur->l == cur->r)
return;
update(cur->lkid, ind);
update(cur->rkid, ind);
}
long long count_swaps(vector<int> s)
{
cerr<<"Does this give an error? Also, cats are soo cute..";
n = s.size()/2;
vector <int> lef[n], rig[n];
int beth[2*n];
for(int i = 0; i<2*n; i++)
{
if(s[i]<0)
{
lef[-s[i]-1].push_back(i);
}
else
{
rig[s[i]-1].push_back(i);
}
}
for(int i = 0; i<n; i++)
{
for(int j = 0; j<int(lef[i].size()); j++)
{
beth[lef[i][j]] = rig[i][j];
beth[rig[i][j]] = lef[i][j];
}
}
rt = new node(0, 2*n-1);
build(rt);
ll cat, Cat = 0;
for(int i = 0; i<2*n; i++)
{
if(beth[i] < i)
continue;
update(rt, i);
update(rt, beth[i]);
cat = query(rt, i, beth[i]);
if(s[i]>0)
cat++;
Cat+=cat;
}
return Cat;
}
