#include "shoes.h"
#include <assert.h>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iostream>
namespace __Sol__ {
using ll = long long;
template<class T> using vec = std::vector<T>;
struct AIB {
vec<int> aib;
AIB( int n ): aib(n + 1, 0) {}
int query( int idx ) {
int ret = 0;
for( int i = idx; i; i &= (i - 1) )
ret += aib[i];
return ret;
}
void update( int idx, int delta ) {
for( int i = idx + 1; i < (int)aib.size(); i += (i & -i) )
aib[i] += delta;
}
};
ll count_swaps( const vec<int> &s ) {
int n = (int)s.size() / 2;
vec<vec<int>> left(n + 1);
vec<vec<int>> right(n + 1);
for( int i = 0; i < 2 * n; i++ )
if( s[i] < 0 )
left[-s[i]].push_back( i );
else
right[+s[i]].push_back( i );
vec<std::pair<int, int>> pairs;
for( int x = 1; x <= n; x++ )
for( int i = 0; i < (int)left[x].size(); i++ )
pairs.emplace_back( left[x][i], right[x][i] );
ll ret = 0;
vec<int> pair(2 * n);
for( auto [a, b]: pairs ){
pair[a] = b;
pair[b] = a;
ret += (a > b);
}
AIB aib(2 * n);
for( int i = 0; i < 2 * n; i++ )
aib.update( i, +1 );
for( int i = 0; i < 2 * n; i++ ){
if( pair[i] < i ) continue;
int j = pair[i];
ret += aib.query( j ) - aib.query( i + 1 );
aib.update( j, -1 );
}
return ret;
}
}
long long count_swaps(std::vector<int> s) { return __Sol__::count_swaps(s); }
