#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define pb push_back
#define eb emplace_back
#define lsb(x) ((x) & (-(x)))
struct fenwick{
vector<int> arr;
int n;
fenwick(int N){
n = N;
arr.resize(N);
}
void update(int X, int V){
X++;
for(; X < n; X += lsb(X)){
arr[X] += V;
}
}
int query(int X){
X++;
if(!X){
return 0;
}
int ans = 0;
for(; X; X -= lsb(X)){
ans += arr[X];
}
return ans;
}
} *fw;
ll count_swaps(std::vector<int> s) {
int n2 = s.size();
int n = n2/2;
fw = new fenwick(n2+1);
vector<pii> m;
m.reserve(n);
vector<vi> p(n+1);
for(int i=0; i<n2; i++){
if(s[i] < 0){
m.eb(-s[i], i);
}
else{
p[s[i]].pb(i);
}
}
for(int i=1; i<=n; i++){
reverse(p[i].begin(), p[i].end());
}
vector<int> c;
c.reserve(n2);
for(int i=0; i<n; i++){
auto& [si, mi] = m[i];
c.pb(mi);
c.pb(p[si].back());
p[si].pop_back();
}
/*for(auto j: c){
cerr << j << ' ';
}*/
ll ans = 0;
for(int i=n2-1; i>=0; i--){
ans += fw->query(c[i]-1);
fw->update(c[i], 1);
}
return ans;
}
