#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 545 , inf = 1e9 + 199;
#include "shoes.h"
ll count_swaps(vector<int> v) {
int n = v.size();
set<int> s;
for(auto& it : v) {
s.insert(abs(it));
}
if(s.size() == 1) {
ll idx = 0, ans = 0;
for(int i = 0; i < n; i++) {
if(v[i] < 0) {
ans += abs(i - idx);
idx += 2;
}
}
return ans;
}
if((n>>1) > 1000) {
n >>=1;
ll ans = 0;
for(ll i = 0; i < n; i++) {
ans += i;
}
return ans;
}
vector<bool> color(n, false);
ll ans = 0;
vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);
for(int i = 0; i < n; i++) {
if(color[i]) {
continue;
}
color[i] = true;
for(int j=i+1;j<n;j++) {
if(color[j] == 0 && v[j] == -v[i]) {
color[j] = true;
int tmp = idx[j] - idx[i] - 1;
if (idx[i]%2 == 0 && v[i] < 0) {
ans += tmp;
}
else {
ans += tmp + 1;
}
break;
}
idx[j]++;
}
}
return ans;
}
