#include "shoes.h"
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define VPII vector<pair<int,int> >
#define F first
#define S second
#define RF(x) freopen(x,"r",stdin)
#define WF(x) freopen(x,"w",stdout)
typedef long long LL;
using namespace std;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
const LL MOD = 1e9+7;
const int SIZE = 1e6+5;
const LL INF = 1LL<<58;
const double eps = 1e-10;
int fw[200009];
void up(int x,int v){
x+=2;
for(;x<200009;x+=x&(-x))fw[x]+=v;
}
int qu(int x){
x+=2;
int ans=0;
for(;x;x-=x&(-x))ans+=fw[x];
return ans;
}
queue<int> pos[200009];//shoes of each type!
int N,H;
bool taken[200009];
long long count_swaps(std::vector<int> s) {
N=SZ(s);
H=N/2;
REP(i,N){
if(s[i]<0)s[i]=-s[i];
else s[i]=H+s[i];
pos[s[i]].push(i);
up(i+1,1); //fw parameters are 0 indexed!!
}
long long ans =0;
REP(i,N){
if(taken[i])continue;
int mi;//matching index
if(s[i]<=H){//left shoe
mi=s[i]+H;
}
else{
mi=s[i]-H;
}
int mpos = pos[mi].front();//matching position
ans += qu(mpos)-qu(i)-(s[i]<=H);//find position of mpos
//printf("ans: %lld\n",ans);
up(i+1,1);up(mpos,-1);
taken[mpos]=taken[i]=1;
pos[mi].pop();
pos[s[i]].pop();
}
return ans;
}
