#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include "shoes.h"
#define MAX_N 200000
using namespace std;
struct shoe_pair {
int left, right;
bool operator < (const shoe_pair &a) const {
return left + right < a.left + a.right;
}
};
struct aib {
long long aib[MAX_N + 1];
void update( int i, int x ) {
while ( i <= MAX_N ) {
aib[i] += x;
i += (i & -i);
}
}
int query( int i ) {
int s;
s = 0;
while ( i > 0 ) {
s += aib[i];
i -= (i & -i);
}
return s;
}
};
int p[2 * MAX_N + 1];
queue <int> q[2 * MAX_N + 2];
shoe_pair pairs[MAX_N];
aib change;
long long count_swaps( vector <int> s ) {
int n, nrPairs, i;
long long nrSwaps;
n = s.size() / 2;
nrPairs = 0;
for ( i = 0; i < 2 * n; i++ ) {
if ( q[-s[i] + n].size() > 0 ) {
if ( s[i] < 0 )
pairs[nrPairs] = { i, q[-s[i] + n].front() };
else
pairs[nrPairs] = { q[-s[i] + n].front(), i };
nrPairs++;
q[-s[i] + n].pop();
} else
q[s[i] + n].push( i );
}
sort( pairs, pairs + n );
for ( i = 0; i < n; i++ ) {
pairs[i].left++;
pairs[i].right++;
p[pairs[i].left] = i;
p[pairs[i].right] = i;
}
nrSwaps = 0;
for ( i = 0; i < n; i++ ) {
nrSwaps += pairs[i].left + 2 * i - change.query( pairs[i].left ) - (2 * i + 1);
change.update( pairs[i].left, 1 );
nrSwaps += pairs[i].right + 2 * i + 1 - change.query( pairs[i].right ) - (2 * i + 2);
change.update( pairs[i].right, 1 );
}
return nrSwaps;
}
