#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100;
int t[4 * N], sum[4 * N], p = 0;
vector <int> S;
void build (int x, int tl, int tr){
if (tl == tr){
t[x] = tl;
}
else{
int mid = (tl + tr)/2;
build(x * 2, tl, mid);
build(x * 2 + 1, mid + 1, tr);
t[x] = t[2 * x] + t[2 * x + 1];
}
}
void update(int l, int r, int x, int tl, int tr){
if (l > r){
return ;
}
else if (l == tl && r == tr){
sum[x]++;
}
else{
//cout << l << " " << r << " " << x << " " << tl << " " << tr << "\n";
int tmid = (tl + tr)/2;
update(l, min(tmid, r), x * 2, tl, tmid);
update(max(l, tmid + 1), r, x * 2 + 1, tmid + 1, tr);
}
}
int get(int num, int x, int tl, int tr){
if (tl == tr){
p+=sum[x];
return t[x] + p;
}
else{
p+=sum[x];
int tmid = (tl + tr)/2;
if (num > tmid)
return get(num, x * 2 + 1, tmid + 1, tr);
else
return get(num, x * 2, tl, tmid);
}
}
long long count_swaps(vector<int> s) {
int ans = 0, n = s.size();
map <int, queue <int>> q;
build(1, 0, n - 1);
for (int i = 0 ; i < n ; i++){
//cout << get(i, 1, 0, n - 1) << "\n";
if (!q[s[i] * -1].empty()){
int cur = q[s[i] * -1].front();
q[s[i] * -1].pop();
ans+=get(i, 1, 0, n - 1) - get(cur, 1, 0, n - 1) - 1;
update(cur, i, 1, 0, n - 1);
if (s[i] < 0)
ans++;
}
else{
q[s[i]].push(i);
}
}
return ans;
}
