#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
/*
4
1 2 3 -4 4 -2 -1 -3
4
1 2 3 -4 -2 4 -1 -3
5
3 2 2 -2 3 2 -3 -2 -2 -3
4
1 2 3 4 -4 -3 -2 -1
5
1 2 3 4 4 -1 -2 -3 -4 -4
5
*/
struct SegTree {
int n;
vector<int> tree;
void build(int sz) {
n = 1;
while(n < sz) {
n *= 2;
}
tree.assign(2*n, 0);
}
void set(int id, int val) {
set_r(0, 0, n, id, val);
}
void set_r(int idx, int l, int r, int& id, int& val) {
if (r - l == 1) {
tree[idx] = val;
return;
}
int mid = (l + r) / 2;
if (id < mid) {
set_r(2*idx+1, l, mid, id, val);
} else {
set_r(2*idx+2, mid, r, id, val);
}
tree[idx] = tree[2*idx+1] + tree[2*idx+2];
}
int sum(int L, int R) {
return sum_r(0, 0, n, L, R);
}
int sum_r(int idx, int l, int r, int& L, int& R) {
if (l >= R || r <= L) return 0;
if (l >= L && R >= r) return tree[idx];
int mid = (l + r) / 2;
int s1 = sum_r(2*idx+1, l, mid, L, R);
int s2 = sum_r(2*idx+2, mid, r, L, R);
return s1 + s2;
}
};
long long count_swaps(std::vector<int> s) {
int n = s.size();
vector<int> a = s;
ll sum = 0;
SegTree st;
st.build(n);
map<int, int> cnt;
vector<int> idx[n+1][2];
for(int i = 0; i < n; i++) {
idx[abs(a[i])][a[i]>0].push_back(i);
}
vector<pair<int, int>> id;
for(int i = 0; i <= n; i++) {
for(int j = 0; j < (int) idx[i][0].size(); j++) {
if (idx[i][0][j] < idx[i][1][j]) {
swap(idx[i][0][j], idx[i][1][j]);
} else {
sum++;
}
id.push_back({idx[i][0][j], idx[i][1][j]});
}
}
sort(id.begin(), id.end());
for(auto i : id) {
sum += (i.first-i.second-1);
sum -= st.sum(i.second, i.first);
st.set(i.first, 1);
st.set(i.second, -1);
}
return sum;
}
