#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
long long count_swaps(std::vector<int> s) {
int n = s.size()/2, orientation_swaps = 0;
long long total_swaps, pairing_swaps = 0;
std::vector<int> pair_index(2*n), prefix1(2*n), prefix2(2*n), prefix3(2*n), BIT_used(n);
std::vector<queue<int>> left_shoe(n), right_shoe(n);
//task 1 : forming pairs
for(int i = 0; i<2*n; i++) {
if(s[i]>0) {
if(!left_shoe[s[i]-1].empty()) {
pair_index[left_shoe[s[i]-1].front()] = i+1;
left_shoe[s[i]-1].pop();
}
else
right_shoe[s[i]-1].push(i);
}
else {
if(!right_shoe[abs(s[i])-1].empty()) {
pair_index[right_shoe[abs(s[i])-1].front()] = i+1;
right_shoe[abs(s[i])-1].pop();
orientation_swaps++;
}
else
left_shoe[abs(s[i])-1].push(i);
}
}
//task 2 : forming prefix1 of "second shoe in pairs before me"
for(int i = 0, count1 = 0, count2 = 0; i<2*n; i++) {
prefix1[i] = count1;
prefix2[i] = count2;
if(pair_index[i])
count2++;
else
count1++;
}
//task 3 : finding prefix3 of "used second shoe in pair before me for each second shoe in pair"
for(int i = 0, j; i<2*n; i++) {
if(pair_index[i]) {
j = prefix1[pair_index[i]-1];
while(j>0) {
prefix3[pair_index[i]-1] += BIT_used[j-1];
j -= (j & (-j));
}
j = prefix1[pair_index[i]-1] + 1;
while(j<=n) {
BIT_used[j-1]++;
j += (j & (-j));
}
}
}
//task 4 : finding swaps for pairing
for(int i = 0; i<2*n; i++)
if(pair_index[i])
pairing_swaps += pair_index[i]-prefix2[pair_index[i]-1]+prefix2[i]+prefix1[pair_index[i]-1]-prefix3[pair_index[i]-1]-i-1;
total_swaps = pairing_swaps + orientation_swaps;
return total_swaps;
}
