#include <bits/stdc++.h>
#include "shoes.h"
typedef long long ll;
const int MAX_N = 1e6 + 42;
int p[MAX_N];
int last[MAX_N];
ll tree[MAX_N];
void add( int x, int v ){
// std::cerr<<" ! "<<x<<"\n";
while( x < MAX_N ){
tree[x] += v;
x += x&(-x);
}
}
int query( int x ){
int nas = 0;
while( x ){
nas += tree[x];
x -= x&(-x);
}
return nas;
}
bool oke[MAX_N];
bool l[MAX_N];
long long count_swaps(std::vector<int> s) {
ll nas = 0;
int n = s.size();
for( int i=1 ; i<=n ; i++ ){
if( s[i-1] < 0 ) l[i] = true;
int curr = abs( s[i-1] );
// std::cerr<<" ! "<<curr<<"\n";
// std::cerr<<last[curr]<<"\n";
if( last[curr] == 0 ) last[curr] = i;
else{
p[i] = last[curr];
p[last[curr]] = i;
last[curr] = 0;
}
add( i, 1 );
}
/*
for( int i=1 ; i<=n ; i++ )
std::cerr<<p[i]<<" ";
std::cerr<<"\n";
*/
for( int i=1 ; i<=n ; i++ ){
while( i<=n and oke[i] ) i++;
if( i > n ) break;
ll currNas = query( p[i] )-1;
if( l[i] ){
// std::cerr<<"l -> -1 \n";
currNas --;
}
// std::cerr<<" ! "<<i<<" "<<p[i]<<" -> "<<currNas<<"\n\n";
nas += currNas;
add( i, -1 );
add( p[i], -1 );
oke[i] = true;
oke[p[i]] = true;
}
return nas;
}
