#include "shoes.h"
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 5;
int n;
ll segt[8 * N];
queue<int>vec[2 * N];
inline int lt(int x){return 2 * x;}
inline int rt(int x){return 2 * x + 1;}
void upd(int nd, int s, int e, int idx) {
if(s > idx || e < idx)
return;
if(s == e) {
segt[nd] += 1;
return;
}
int m = (s + e) / 2;
upd(lt(nd), s, m, idx);
upd(rt(nd), m + 1, e, idx);
segt[nd] = segt[lt(nd)] + segt[rt(nd)];
}
ll query(int nd, int s, int e, int l, int r) {
if(s > r || e < l)
return 0;
if(s >= l && e <= r)
return segt[nd];
int m = (s + e) / 2;
return query(lt(nd), s, m, l, r) + query(rt(nd), m + 1, e, l, r);
}
long long count_swaps(vector<int> s) {
ll ans = 0;
n = s.size();
for(int a = 0; a < n; a++){
s[a] += n / 2;
vec[s[a]].push(a);
}
for(int a = 0; a < n; a++) {
if(query(1, 1, n, a, a) == 1)
continue;
int target;
if(s[a] > n)
target = (-(s[a] - n / 2) + n / 2);
else
target = (-(s[a] - n / 2) + n / 2);
int idx = vec[target].front();
vec[target].pop();
vec[s[a]].pop();
ll toadd;
if(s[a] < target)
toadd = (idx - a - 1 - query(1, 1, n, a, idx));
else
toadd = (idx - a - query(1, 1, n, a, idx));
ans += toadd;
// printf("%d %d %d %d %lld\n", a, s[a], target, idx, toadd);
upd(1, 1, n, idx);
}
return ans;
}
