#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll maxN = 2e5+5;
vector<ll> t;
void build(ll v, ll tl, ll tr) {
if (tl == tr) {
t[v] = 1;
} else {
ll tm = (tl + tr) / 2;
build(v*2, tl, tm);
build(v*2+1, tm+1, tr);
t[v] = t[v*2] + t[v*2+1];
}
}
ll sum(ll v, ll tl, ll tr, ll l, ll r) {
if (l > r)
return 0;
if (l == tl && r == tr) {
return t[v];
}
ll tm = (tl + tr) / 2;
return sum(v*2, tl, tm, l, min(r, tm))
+ sum(v*2+1, tm+1, tr, max(l, tm+1), r);
}
void update(ll v, ll tl, ll tr, ll pos, ll new_val) {
if (tl == tr) {
t[v] = new_val;
} else {
ll tm = (tl + tr) / 2;
if (pos <= tm)
update(v*2, tl, tm, pos, new_val);
else
update(v*2+1, tm+1, tr, pos, new_val);
t[v] = t[v*2] + t[v*2+1];
}
}
ll count_swaps(vector<int>v){
ll n = v.size();
t.assign(4*n+5, 0);
build(1, 1, n);
map<ll, vector<ll> > m;
for(ll i = 0; i < n; i++) {
m[v[i]].push_back(i+1);
}
ll res = 0;
vector<pair<ll, ll> > pairs;
for(ll i = 0; i < maxN; i++) {
for(ll j = 0; j < (ll)m[i].size(); j++) {
pairs.push_back({m[-i][j], m[i][j]});
if(m[-i][j] > m[i][j]) {
res++;
swap(pairs.back().first, pairs.back().second);
}
}
}
sort(pairs.begin(), pairs.end());
for(auto p : pairs) {
res += sum(1, 1, n, p.first+1, p.second-1);
update(1, 1, n, p.second+1, 0);
}
return res;
}
