#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool com(pair<int,int> a, pair<int,int> b){
return min(a.first,a.second)<min(b.first,b.second);
}
vector<int> tree;
vector<int> ind;
void build(int l, int r, int p){
if(l == r)ind[l] = p;
else{
build(l,(l+r)/2,p*2);
build((l+r)/2+1,r,p*2+1);
}
}
void add(int r, int p, int lb, int rb){
if(rb <= r){tree[p]++;return;}
if(lb > r)return;
add(r,p*2,lb,(rb+lb)/2);
add(r,p*2+1,(rb+lb)/2+1,rb);
}
int check(int p){
if(p == 0)return 0;
return check(p/2)+tree[p];
}
ll count_swaps(vector<int> s) {
int n = s.size()/2;
tree.resize(8*n);
ind.resize(n*2+1);
build(0,n*2-1,1);
vector<vector<pair<int,int>>> shoe(n*2+1);
vector<pair<int,int>> seg;
vector<int> num(n*2+1,0);
for(int i = 0; i < n*2; ++i){
if(num[abs(s[i])] == (int)shoe[abs(s[i])].size()){
shoe[abs(s[i])].push_back({s[i],i});
continue;
}
if(shoe[abs(s[i])][num[abs(s[i])]].first == s[i]){
shoe[abs(s[i])].push_back({s[i],i});
continue;
}
if(s[i] > 0)seg.push_back({i,shoe[abs(s[i])][num[abs(s[i])]].second});
else seg.push_back({shoe[abs(s[i])][num[abs(s[i])]].second,i});
num[abs(s[i])]++;
}
sort(seg.begin(),seg.end(),com);
ll ans = 0;
for(int i = 0; i < (int)seg.size(); ++i){
int x = max(seg[i].first,seg[i].second);
int y = x+check(ind[x]);
add(x,1,0,n*2-1);
ans+=y-(i*2+1);
ans+=seg[i].first < seg[i].second;
}
return ans;
}
