#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
typedef long long ll;
const int N = 2e5 + 20;
int t[4 * N];
void inc(int v, int tl, int tr, int l, int r){
if(l > r)
return;
if(tl == l && tr == r){
t[v] ++;
return;
}
int tm = (tl + tr) / 2;
inc(v * 2, tl, tm, l, min(r, tm));
inc(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
}
void build(int v, int tl, int tr){
if(tl == tr){
t[v] = tl;
return;
}
int tm = (tl + tr) / 2;
build(v * 2, tl, tm);
build(v * 2 + 1, tm + 1, tr);
}
int get(int v, int tl, int tr, int pos){
if(tl == tr)
return t[v];
int tm = (tl + tr) / 2;
if(pos <= tm)
return get(v * 2, tl, tm, pos) + t[v];
else
return get(v * 2 + 1, tm + 1, tr, pos) + t[v];
}
ll count_swaps(vector<int> s) {
int n = s.size();
map<int, vector<int>> m;
for(int i = n - 1; i >= 0; i --)
m[s[i]].push_back(i);
build(1, 0, n - 1);
ll result = 0;
for(int i = 0; i < n; i ++){
if(m[s[i]].empty() || m[s[i]].back() != i)
continue;
int j = m[-s[i]].back();
m[s[i]].pop_back();
m[-s[i]].pop_back();
int x = get(1, 0, n - 1, i);
int y = get(1, 0, n - 1, j);
// cout << i << " " << j << " : " << x << " " << y << endl;
result += (y - x) - 1;
if(s[i] > 0)
++ result;
inc(1, 0, n - 1, i, j);
}
// cout << result << endl;
return result;
}
