#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<bool> vb;
// Range sum point update segtree
struct Tree {
Tree *lt, *rt;
int l, r;
int v;
Tree(int a_l, int a_r): lt(nullptr), rt(nullptr), l(a_l), r(a_r), v(0) {};
void combine() {
v = lt->v + rt->v;
}
void build(const vi& a) {
if(l == r) {
v = a[l];
return;
}
int m = (l + r) >> 1;
lt = new Tree(l, m);
rt = new Tree(m + 1, r);
lt->build(a);
rt->build(a);
combine();
}
int qry(int ql, int qr) {
if(ql > r || qr < l) return 0;
if(ql == l && qr == r) return v;
int m = (l + r) >> 1;
return lt->qry(ql, min(qr, m)) + rt->qry(max(ql, m + 1), qr);
}
void upd(int i, int nv) {
if(i > r || i < l) return;
if(l == r) {
v = nv;
return;
}
int m = (l + r) >> 1;
if(i <= m) lt->upd(i, nv);
else rt->upd(i, nv);
combine();
}
};
ll count_swaps(vi s) {
int n = s.size();
vi init_tree_vals(n, 1);
Tree tr(0, n - 1);
tr.build(init_tree_vals);
// store the indices at which each size occurs
typedef map<int, set<int>> map_set;
map_set pos;
for(int i = 0; i < n; i++) {
if(pos.count(s[i]) == 0) {
// Create a new entry
pos[s[i]] = set<int>();
}
pos[s[i]].insert(i);
}
ll num_swaps = 0ll;
// greedily match the shoes
for(int i = 0; i < n; i++) {
if(tr.qry(i, i) == 0) continue;
if(s[i] > 0) num_swaps++;
int other_pos = *pos[-s[i]].begin();
int num_intermediate = tr.qry(i + 1, other_pos - 1);
num_swaps += (ll)num_intermediate;
tr.upd(i, 0);
tr.upd(other_pos, 0);
pos[s[i]].erase(i);
pos[-s[i]].erase(other_pos);
}
return num_swaps;
}
