#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct sgt {
int n, ql, qr, qi, qx;
vector <int> t;
void init(int sz) {
n = sz + 2;
t.assign(n << 2, 0);
}
void update(int v, int l, int r) {
if (l == r) {
t[v] += qx;
return;
}
int m = l + r >> 1;
if (qi <= m)
update(v << 1, l, m);
else
update(v << 1 | 1, m + 1, r);
t[v] = t[v << 1] + t[v << 1 | 1];
}
void update(int l, int r) {
qi = l, qx = 1;
update(1, 0, n - 1);
qi = r, qx = -1;
update(1, 0, n - 1);
}
int get(int v, int l, int r) {
// cout << l << ' ' << r << '\n' << flush;
if (l > qi)
return 0;
if (r <= qi)
return t[v];
int m = l + r >> 1;
return get(v << 1, l, m) + get(v << 1 | 1, m + 1, r);
}
int get(int i) {
qi = i;
return get(1, 0, n - 1);
}
};
struct Fenwick{
vector<int> tr;
int sz;
Fenwick(int N){
tr.resize(N+1);
sz=N;
}
void add(ll i, ll x){
for (; i<=sz; i+=(-i&i)) tr[i]+=x;
}
ll get(ll i){
ll sum=0;
for (; i; i-=(i&-i)) sum+=tr[i];
return sum;
}
};
long long count_swaps(vector<int> s) {
int n = s.size(), x;
ll ans = 0, res = 0;
vector <int> v = s;
// cin >> n;
// sgt st;
// st.init(n);
sgt st;
st.init(n);
Fenwick tr(n+2);
vector <deque <int>> p(n + 1, deque <int>()), m(n + 1, deque <int>());
for (int i = 0; i < n; i++) {
// cin >> x;
x = v[i];
// cout << i << "i ";
if (x > 0) {
if (!m[x].empty()) {
int it = m[x].front(); m[x].pop_front();
int l = it + st.get(it), r = i;
ans += r - l - 1;
st.update(it, r + 1);
// cout << it << ' ' << l << ' ' << r << '\n';
} else {
p[x].push_back(i);
}
} else {
x = -x;
if (!p[x].empty()) {
int it = p[x].front(); p[x].pop_front();
int l = it + st.get(it), r = i;
ans += r - l;
// cout << it << ' ' << l << ' ' << r << '\n';
st.update(it, r + 1);
} else {
m[x].push_back(i);
}
}
}
return res;
}
