#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz size()
#define all(x) x.begin(), x.end()
#define F first
#define S second
typedef pair < int, int > pii;
typedef vector < int > vi;
typedef vector < vi > vvi;
int t[800400];
void upd (int v, int l, int r, int pos) {
if (l > pos || r < pos){
return;
}
if (l == r) {
t[v] = 1;
return;
}
int mid = (l + r) / 2;
upd(2 * v, l, mid, pos);
upd(2 * v + 1, mid + 1, r, pos);
t[v] = t[2 * v] + t[2 * v + 1];
}
int get_sum (int v, int l, int r, int tl, int tr) {
if (l > tr || r < tl) {
return 0;
}
if (l >= tl && r <= tr) {
return t[v];
}
int mid = (l + r) / 2;
return get_sum(2 * v, l, mid, tl, tr) + get_sum(2 * v + 1, mid + 1, r, tl, tr);
}
long long count_swaps(vector<int> b) {
int n = b.sz;
int a[n + 7];
int used[n + 7];
for (int i = 0; i < n; i++) {
a[i + 1] = b[i];
used[i + 1] = 0;
}
map <int, deque<int> > m;
for (int i = 1; i <= n; i++) {
m[a[i]].pb(i);
}
long long cnt = 0, ans = 0;
for (int i = 1; i <= n; i++) {
if (used[i]) {
continue;
}
if (a[i] > 0) {
int pos = m[-a[i]].front();
cnt = get_sum (1, 1, n, i, pos);
ans += pos - i - cnt;
used[pos] = 1;
upd(1, 1, n, pos);
m[a[i]].pop_front();
m[-a[i]].pop_front();
}
else {
int pos = m[-a[i]].front();
cnt = get_sum (1, 1, n, i, pos);
ans += pos - i - 1 - cnt;
used[pos] = 1;
upd(1, 1, n, pos);
m[a[i]].pop_front();
m[-a[i]].pop_front();
}
// cout << i << " " << ans << "\n";
}
return ans;
}
/*
signed main() {
vi a;
a.pb(-2);
a.pb(2);
a.pb(2);
a.pb(-2);
a.pb(-2);
a.pb(2);
cout << count_swaps(a);
}
*/
