#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
#define num long long
#define idata vector<int>
#define di pair<int, int>
struct PosM {
set<di> u;
void insert (int type, int pos) {
u.insert({ type, pos });
}
int find (int type) {
di data = *u.lower_bound({ type, -1 });
u.erase(data);
return data.second;
}
};
PosM pos_query;
struct SegTree {
vector<int> tree;
int size, start, height;
SegTree (int ps) {
size = ps;
height = ceil(log2(ps));
start = 1 << height;
tree.resize(start << 1);
}
void update (int l, int r, int delta) {
l += start;
r += start;
while (l < r) {
if ((l & 1) == 1) tree[l] += delta;
if ((r & 1) == 0) tree[r] += delta;
l = (l + 1) >> 1;
r = (r - 1) >> 1;
}
if (l == r) tree[l] += delta;
}
int query (int index) {
int res = 0;
index += start;
while (index != 0) {
res += tree[index];
index >>= 1;
}
return res;
}
};
long long count_swaps (idata shoe_array) {
int nbShoes = shoe_array.size();
vector<di> displacements;
for (int idShoe = 0; idShoe < nbShoes; idShoe ++) {
if (shoe_array[idShoe] > 0)
pos_query.insert(shoe_array[idShoe], idShoe);
}
num answer = 0;
for (int idShoe = 0; idShoe < nbShoes; idShoe ++) {
if (shoe_array[idShoe] < 0) {
int q = pos_query.find( - shoe_array[idShoe] );
if (q < idShoe) answer ++;
displacements.push_back({ min(idShoe, q), max(idShoe, q) });
}
}
SegTree tree(nbShoes);
for (di displ : displacements) {
int x = displ.first;
int y = displ.second;
int rx = x + tree.query(x);
int ry = y + tree.query(y);
answer += ry - rx - 1;
tree.update(x, y, 1);
}
return answer;
}
/*int main () {
int nbNodes;
cin >> nbNodes;
idata s;
for (int i = 0; i < nbNodes; i ++) {
int x;
cin >> x;
s.push_back(x);
}
cout << count_swaps(s);
}*/
