#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
long long count_swaps(std::vector<int> s) {
vector<pair<int, int>> range;
int sum = 0, prev = 1, n = s.size();
s.emplace_back(0);
for (int i = n; i > 0; i--) s[i] = s[i-1];
vector<int> fw(n+1, 0);
function<void(int, int)> update = [&](int x, int v) {
while (x <= n) fw[x] += v, x += x & -x;
};
function<ll(int)> query = [&](int x) {
ll res = 0;
while (x > 0) res += fw[x], x -= x & -x;
return res;
};
for (int i = 1; i <= n; i++) update(i, i), update(i+1, -i);
map<int, deque<int>> l, r;
for (int i = 1; i <= n; i++) {
if (s[i] < 0) l[-s[i]].emplace_back(i);
else r[s[i]].emplace_back(i);
}
ll ans = 0;
for (int i = 1; i <= n; i++) {
int sz = abs(s[i]);
if (s[i] < 0) {
if (l[sz].empty() || l[sz].front() != i) continue;
int t = r[sz].front();
ans += query(t) - query(i) - 1;
update(1, 1);
update(t+1, -1);
} else {
if (r[sz].empty() || r[sz].front() != i) continue;
int t = l[sz].front();
ans += query(t) - query(i);
update(1, 1);
update(t+1, -1);
}
l[sz].pop_front(), r[sz].pop_front();
}
return ans;
}
