#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
#define FOR(i,x,y) for(int i=(int)(x);i<(int)(y);++i)
#define FORE(i,x,y) for(int i=(int)(x);i<=(int)(y);++i)
#define FORD(i,x,y) for(int i=(int)(x);i>=(int)(y);--i)
#define PB push_back
#define ST first
#define ND second
typedef long long ll;
typedef pair<int,int> pii;
const int MAXT=(1<<19)+7;
const int MAXN=2e5+7;
int n;
int t[MAXT];
int lazy[MAXT];
bool vis[MAXN];
vector<int> pos[MAXN];
void Bld(int v,int vl,int vr){
if(vl==vr){
t[v]=vl;
}else{
int vm=(vl+vr)/2;
Bld(v*2,vl,vm);
Bld(v*2+1,vm+1,vr);
}
}
void Push(int v){
t[v*2]+=lazy[v];
lazy[v*2]+=lazy[v];
t[v*2+1]+=lazy[v];
lazy[v*2+1]+=lazy[v];
lazy[v]=0;
}
void Add(int v,int vl,int vr,int l,int r,int val){
if(l>r)return;
if(l==vl&&r==vr){
t[v]+=val;
lazy[v]+=val;
}else{
Push(v);
int vm=(vl+vr)/2;
Add(v*2,vl,vm,l,min(vm,r),val);
Add(v*2+1,vm+1,vr,max(l,vm+1),vr,val);
}
}
int Qry(int v,int vl,int vr,int vq){
if(vl==vr){
return t[v];
}else{
int vm=(vl+vr)/2;
Push(v);
if(vq<=vm)return Qry(v*2,vl,vm,vq);
else return Qry(v*2+1,vm+1,vr,vq);
}
}
long long count_swaps(std::vector<int> s) {
n=s.size();
FORD(i,n-1,0){
if(s[i]>0)pos[s[i]*2].PB(i);
else pos[s[i]*(-2)-1].PB(i);
}
ll ans=0;
Bld(1,0,n-1);
FOR(i,0,n){
int x,y;
if(s[i]>0)x=s[i]*2,y=x-1;
else x=s[i]*(-2)-1,y=x+1;
if(pos[x].empty()||pos[x].back()!=i)continue;
int xpos=Qry(1,0,n-1,pos[x].back());
int ypos=Qry(1,0,n-1,pos[y].back());
if(x&1){
ans+=ypos-xpos-1;
}else{
ans+=ypos-xpos;
}
Add(1,0,n-1,pos[y].back(),n-1,-1);
pos[x].pop_back();
pos[y].pop_back();
}
return ans;
}
/*
2
2 1 -1 -2
3
-2 2 2 -2 -2 2
3
3 -1 2 1 -3 -2
4
3 -1 2 1 -3 -4 -2 4
5
1 2 3 4 5 -5 -4 -3 -2 -1
3
1 2 3 -3 -2 -1
1
-1 1
*/
