#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct segtree{
int n; vector<int> t;
segtree(vector<int> &a): n(a.size()){
t.resize(2*n);
for(int i = 0; i<n; i++) t[i+n] = a[i];
for(int i = n-1; i > 0; i--) t[i] = t[i<<1] + t[(i<<1) | 1];
}
void upd(int i, int k){
for(t[i+=n] = k; i>>=1; ) t[i] = t[i<<1] + t[(i<<1) | 1];
return;
}
int q(int l, int r){
int sol = 0;
for(l+=n, r+=n; l<=r; l>>=1, r>>=1){
if(l&1) sol += t[l++];
if(!(r&1)) sol += t[r--];
}
return sol;
}
};
long long count_swaps(std::vector<int> s) {
map<int, vector<int>> idx;
int n = (int)s.size();
for(int i = 0; i<n; i++) idx[s[i]].push_back(i);
map<int, int> point;
for(int i = 0; i<n; i++) point[s[i]] = 0;
vector<int>vv(n, 1);
segtree sg(vv);
long long sol = 0;
vector<bool> vis(n, 0);
for(int i = 0; i<n; i++){
if(vis[i]) continue;
int r = idx[-s[i]][point[-s[i]]];
point[s[i]]++;
point[-s[i]]++;
if(r > i+1){
sol += sg.q(i+1, r-1);
}
if(s[i] > 0) sol++;
sg.upd(i, 0);
vis[i] = 1;
sg.upd(r, 0);
vis[r] = 1;
}
return sol;
}
