#include "shoes.h"
#include <bits/stdc++.h>
#define pb push_back
// #define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;
struct fenwick{
int n;
vector<int> fen;
fenwick(int n) : n(n), fen(n){}
void upd(int pos, int val){
for(; pos < n; pos |= pos + 1)
fen[pos] += val;
}
int index(int ind){
int ret = 0;
for(; ind >= 0; ind = (ind & (ind + 1)) - 1)
ret += fen[ind];
return ret;
}
};
ll count_swaps(vector<int> v){
int n = v.size() / 2;
set<int> negative;
set<int> positive;
vector<vector<int>> posoccurence(n + 1), negoccurence(n + 1);
for(int i = 2 * n - 1; i >= 0; i--){
if(v[i] < 0) negative.insert(i);
else posoccurence[v[i]].pb(i), positive.insert(i);
}
for(int i = 0; i < 2 * n; i++)
if(v[i] < 0) negoccurence[-v[i]].pb(i);
fenwick fen(2 * n);
ll ans = 0;
for(int i = 0; i < 2 * n; i++)
fen.upd(i, 1);
for(int i = 0; i < n; i++){
if(fen.index(*negative.begin()) != 1 && fen.index(2 * n - 1) == fen.index(*prev(positive.end()))){
int pos = *prev(positive.end());
positive.erase(pos);
int val = v[pos];
fen.upd(pos, -1);
pos = fen.index(pos);
ans += fen.index(2 * n - 1) - pos;
int neg = negoccurence[val].back(); negoccurence[val].pop_back();
fen.upd(neg, -1);
negative.erase(neg);
neg = fen.index(neg);
ans += fen.index(2 * n - 1) - neg;
}
else{
int neg = *negative.begin(); negative.erase(negative.begin());
int val = v[neg];
fen.upd(neg, -1);
neg = fen.index(neg);
ans += neg;
int pos = posoccurence[-val].back();
posoccurence[-val].pop_back();
fen.upd(pos, -1);
positive.erase(pos);
pos = fen.index(pos);
ans += pos;
}
}
return ans;
}
