#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define SIZE 262144
int tree[SIZE*2];
int sum(int a,int b){
a+=SIZE;b+=SIZE;int s=0;
while(a<=b){
if(a%2==1)s+=tree[a++];
if(b%2==0)s+=tree[b--];
a/=2;b/=2;
}
return s;
}
void add(int a,int b){
a+=SIZE;tree[a]+=b;
for(a/=2;a>=1;a/=2){
tree[a]=tree[2*a]+tree[2*a+1];
}
}
long long count_swaps(std::vector<int> s) {
vector<int> l[100005];vector<int> r[100005];int n=s.size();
for(int i=0;i<n;i++){
if(s[i]<0)l[-s[i]].push_back(i);
else r[s[i]].push_back(i);
add(i,1);
}
for(int i=0;i<100005;i++){sort(l[i].rbegin(),l[i].rend());sort(r[i].rbegin(),r[i].rend());}
long long t=0;
for(int i=0;i<n;i++){
//cerr<<r[-s[i]].empty()<<endl;
if(s[i]==SIZE)continue;
if(s[i]<0){
if(r[-s[i]].empty()){cerr<<i<<endl;exit(1);}
int k;int z=SIZE;while(z==SIZE||k==i){k=r[-s[i]].back();r[-s[i]].pop_back();z=s[k];}
//cerr<<i+1<<' '<<k-1<<endl;
t+=sum(i+1,k-1);add(k,-1);s[i]=SIZE;s[k]=SIZE;
}
else {
if(l[s[i]].empty()){cerr<<i<<endl;exit(1);}
int k;int z=SIZE;while(z==SIZE||k==i){k=l[s[i]].back();l[s[i]].pop_back();z=s[k];}
//cerr<<i<<' '<<k-1<<endl;
t+=sum(i,k-1);add(k,-1);s[i]=SIZE;s[k]=SIZE;
}
}
return t;
}
/*int main(){
int n;cin>>n;while(n--){int a,b;cin>>a>>b;add(a,b);}cin>>n;while(n--){int a,b;cin>>a>>b;cout<<sum(a,b)<<endl;}
}*/
