#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
struct SegTree{
int N;
const int NEU=0;
vector<int>tree;
int merge(int a,int b){
return a+b;
}
SegTree(int n){
N=1;
while(N<n) N<<=1;
tree.assign(N<<1,NEU);
}
void update(int v,int l,int r,int id,int x){
if(l>id || id>=r) return;
if(r-l==1){
tree[v]+=x;
return;
}
int mid=(l+r)>>1;
update(v<<1,l,mid,id,x);
update(v<<1|1,mid,r,id,x);
tree[v]=merge(tree[v<<1],tree[v<<1|1]);
}
void update(int id,int x){
return update(1,0,N,id,x);
}
int get(int v,int l,int r,int ql,int qr){
if(l>=qr || ql>=r) return NEU;
if(l>=ql && qr>=r) return tree[v];
int mid=(l+r)>>1;
int a=get(v<<1,l,mid,ql,qr);
int b=get(v<<1|1,mid,r,ql,qr);
return merge(a,b);
}
int get(int l,int r){
if(r<=l) return 0;
return get(1,0,N,l,r);
}
};
long long count_swaps(vector<int> s) {
int n=s.size();
map<int,deque<int>>last;
long long ans=0;
SegTree S(n+1);
for(int i=0;i<n;i++){
if(last[-s[i]].size()>0){
ans+=S.get(last[-s[i]].front()+1,i+1)+(s[i]<0);
S.update(last[-s[i]].front(),1);
last[-s[i]].pop_front();
}
else{
last[s[i]].push_back(i+1);
S.update(i+1,1);
}
}
return ans;
}
// 2
//-1 1 2 -2
