#include "shoes.h"
#include <vector>
#include <deque>
#include <iostream>
#define ll long long
#define F first
#define S second
using namespace std;
vector<ll> num_swaps(5e5+8,0);
ll get_swaps(int pos,int l,int r,int ql,int qr){
if(ql > r || qr<l) return 0;
if(r<=qr && l>=ql)
return num_swaps[pos];
int mid = (l+r)/2;
return get_swaps(2*pos+1,l,mid,ql,qr) + get_swaps(2*pos+2,mid+1,r,ql,qr);
}
void update_swaps(int pos,int l,int r,int index,int val){
num_swaps[pos] += val;
if(index == l && l == r){
return;
}
int mid = (l+r)/2;
if(index <= mid){
update_swaps(2*pos+1,l,mid,index,val);
}else{
update_swaps(2*pos+2,mid+1,r,index,val);
}
}
long long count_swaps(std::vector<int> s) {
ll ans = 0;
vector<deque<int>> arr(2e5+10);
int n = s.size();
for(int i = 0;i<n;i++){
int left = 0;
if(s[i] < 0)left = 1;
// if(left)cerr << "left ";
// else cerr << "right ";
// cerr << s[i] << " " << arr[-s[i]+1e5].size() << " ";
if(arr[-s[i]+1e5].size() > 0){
int a = arr[-s[i]+1e5][0];
arr[-s[i]+1e5].pop_front();
// cerr << a.F << " " << a.S << " " << cnt << endl;
// cout << ans << endl;
ans += i - a - get_swaps(0,0,n-1,a,i);
update_swaps(0,0,n-1,i,1);
update_swaps(0,0,n-1,a,-1);
if(left == 0)ans -= 1;
}else{
// cerr << s[i]+1e5 << " " << i << " " << cnt << endl;
arr[s[i]+1e5].push_back(i);
}
}
return ans;
}
