#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void update(vector<ll>&seg,ll ind,ll l,ll r,ll givenpos){
if(l==r){
seg[ind]+=1;
return;
}
ll mid = l + (r-l)/2;
if(mid>=givenpos){
update(seg,2*ind+2,mid+1,r,givenpos);
}else{
update(seg,2*ind+1,l,mid,givenpos);
}
seg[ind] = seg[2*ind+1] + seg[2*ind+2];
return;
}
ll query(vector<ll>&seg,ll ind,ll l,ll r,ll left,ll right){
if(l>right||r<left) return 0;
if(l<=left&&r>=right) return seg[ind];
ll mid = l + (r-l)/2;
return query(seg,2*ind+1,l,mid,left,right) + query(seg,2*ind+2,mid+1,r,left,right);
}
long long count_swaps(std::vector<int> s) {
long long ans = 0;
long long n = s.size();
vector<vector<ll>> left(n+10),right(n+10);
for(ll i=0;i<n;i++){
ll sz = abs(s[i]);
if(s[i]<0){
left[sz].push_back(-i);
}else{
right[sz].push_back(-i);
}
}
for(ll i=0;i<n;i++){
sort(left[i].begin(),left[i].end());
sort(right[i].begin(),right[i].end());
}
vector<ll> seg(6*n);
map<ll,ll> used;
for(ll i=0;i<n;i++){
if(!used[i]){
ll sz = abs(s[i]);
ll tmpA = 0;
if(s[i]<0){
ll pos = right[sz].back();
pos *= -1;
right[sz].pop_back();
left[sz].pop_back();
ll am = pos - i;
am = am - query(seg,0,0,n-1,i,pos);
update(seg,0,0,n-1,pos);
used[pos]=1;
used[i]=1;
tmpA = am;
}else{
ll pos = left[sz].back();
pos *= -1;
right[sz].pop_back();
left[sz].pop_back();
ll am = pos - i;
am = am - query(seg,0,0,n-1,i,pos);
update(seg,0,0,n-1,pos);
used[pos]=1;
used[i]=1;
tmpA = am;
}
if(i%2==0){
if(s[i]>0) tmpA++;
}else{
if(s[i]<0) tmpA++;
}
ans+=tmpA;
}
}
return ans;
}
