#include "shoes.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int mxN = 2e5;
ll ft[mxN+1];
void update(int i, ll x) {
for(; i <= mxN; i += i&-i) {
ft[i] += x;
}
}
ll query(int i) {
ll r = 0;
for(; i; i -= i&-i) {
r += ft[i];
}
return r;
}
ll count_swaps(vector<int> s) {
int n = (int)s.size();
vector<pair<int, int>> mesta[n+1];
for(int i = 0; i < n; ++i) {
mesta[abs(s[i])].push_back({s[i], i});
}
for(int i = 1; i <= n; ++i) {
sort(mesta[i].begin(), mesta[i].end());
}
ll ans = 0;
vector<pair<int, int>> parovi;
for(int i = 1; i <= n/2; ++i) {
for(int j = 0; j < (int)mesta[i].size()/2; ++j) {
int l = mesta[i][j].second;
int r = mesta[i][j+mesta[i].size()/2].second;
if(l > r) {
++ans;
swap(l, r);
}
parovi.push_back({l+1, r+1});
}
}
sort(parovi.begin(), parovi.end());
for(int i = 1; i <= n; ++i)
update(i, 1);
for(auto z : parovi) {
ans += query(z.second-1) - query(z.first);
update(z.first, -1);
update(z.second, -1);
}
return ans;
}
