#include "shoes.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 2e5+5;
long long t[4*N];
long long fix[N];
vector <vector <int>> v(N);
void update(int node, int tl, int tr,int pos) {
if (tl == tr) {
t[node]++;
return;
}
int mid = (tl+tr)/2;
if (pos <= mid) {
update(node*2,tl,mid,pos);
} else {
update(node*2+1,mid+1,tr,pos);
}
t[node] = t[node*2]+t[node*2+1];
}
long long getsum(int node, int tl, int tr, int l, int r) {
if (l > r) return 0;
if (tl == l && tr == r) {
return t[node];
}
int mid = (tl+tr)/2;
return (getsum(node*2,tl,mid,l,min(r,mid))+getsum(node*2+1,mid+1,tr,max(mid+1,l),r));
}
long long count_swaps(std::vector<int> s) {
long long n = s.size();
s.insert(s.begin(),0);
for (int i = 1; i <= n; i++) {
v[s[i]+n/2].pb(i);
}
long long op = 0;
for (int i = 1; i <= n; i++) {
if (fix[i]) continue;
long long a = s[i];
long long b = -s[i]+n/2;
int l = 0; int r = v[b].size()-1;
int ib;
while (l <= r) {
int mid = (l+r)/2;
if (v[b][mid] > i) {
ib = v[b][mid];
r = mid - 1;
} else {
l = mid + 1;
}
}
op += (ib-i-1-getsum(1,1,n,i,ib));
update(1,1,n,ib);
if (a>=0) op++;
fix[ib]++;
}
return op;
}
