#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);
vi pp[n2+1];
auto p = pp + n;
for(int i=0; i<n2; i++){
p[s[i]].pb(i);
}
for(int i=-n; i<=n; i++){
reverse(p[i].begin(), p[i].end());
}
vector<bool> vis(n2);
vector<int> c;
c.reserve(n2);
for(int i=0; i<n2; i++){
if(vis[i]) continue;
int c1 = i, c2 = p[-s[i]].back();
vis[c2] = 1;
p[-s[i]].pop_back();
p[s[i]].pop_back();
if(s[i] > 0){
swap(c1, c2);
}
c.pb(c1);
c.pb(c2);
}
/*for(auto j: c){
cerr << j << ' ';
}*/
//c = {3, 0, 5, 1, 2, 4, 7, 6};
ll ans = 0;
for(int i=n2-1; i>=0; i--){
ans += fw->query(c[i]-1);
fw->update(c[i], 1);
}
return ans;
}
