#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct segtree
{
int size;
vector<int> values;
void init(int n) {
size=1;
while(size<n)size*=2;
values.resize(2*size);
}
int calc(int i, int x, int qLeft, int qRight) {
if (qLeft>i || qRight<i) return -1;
if (qRight-qLeft == 1) return values[x];
int mid=(qLeft+qRight) / 2;
int s1=calc(i, 2*x, qLeft, mid);
if (s1==-1) {
s1 = calc(i, 2*x + 1, mid, qRight);
}
return values[x]+s1;
}
int calc(int i) {
return calc(i, 1, 0, size);
}
void update(int x, int left, int right, int qLeft, int qRight) {
if (qLeft>=right || qRight<=left) return;
if (qLeft>=left && qRight<=right) {
values[x]++;
return;
}
int mid=(qLeft+qRight) / 2;
update(x*2, left, right, qLeft, mid);
update(x*2 + 1, left, right, mid, qRight);
}
void update(int left, int right) {
update(1, left, right, 0, size);
}
};
long long count_swaps(vector<int> s) {
int n=s.size();
vector<int> cnt[(int)2*n+5];
vector<int> used(2*n+5, 0);
vector<bool> visited(2*n+5, false);
long long comp=0;
segtree st;
st.init(n);
for (int i = 0; i < n; ++i)
{
cnt[s[i]+n].push_back(i);
}
for (int i = 0; i < n; ++i)
{
if (visited[i]) continue;
int recherche=(-1*s[i])+n;
int j=cnt[recherche][used[recherche]];
comp-=(st.calc(i)-st.calc(j));
//cout << i << ", " << j << ": " << st.calc(i) << " " << st.calc(j) << endl;
st.update(i, j);
if (s[i]<0) comp--;
comp+=j-i;
visited[j]=true;
used[recherche]++;
used[s[i]+n]++;
}
return comp;
}
