#include <bits/stdc++.h>
#include "shoes.h"
#ifdef GUDEB
#define D(x) cerr << #x << ": " << (x) << '\n';
#define ifdeb if(true)
#else
#define D(x) ;
#define ifdeb if(false)
#endif
#define all(x) begin(x), end(x)
using namespace std;
using ull = unsigned long long;
using ll = long long;
// #define int ll;
int it[700000];
deque<int> lsl[100001];
deque<int> rsl[100001];
int n;
int l;
int query(int f, int t) {
f += l;
t += l;
int r = 0;
while(f < t) {
if(f&1) r += it[f++];
if(t&1) r += it[--t];
f /= 2;
t /= 2;
}
return r;
}
void pset(int s, int x) {
s += l;
it[s] = x;
s /= 2;
while(s > 0) {
it[s] = it[2*s] + it[2*s+1];
s /= 2;
}
}
ll count_swaps(vector<int> ss) {
n = ss.size();
l = 1;
ll ret = 0;
for(int i = 0; i < n; ++i) {
if(ss[i] > 0) rsl[ss[i]].push_back(i);
else lsl[-ss[i]].push_back(i);
}
while(l < n) l *= 2;
for(int i = 0; i < n; ++i)
it[l+i] = 1;
for(int i = l-1; i > 0; --i)
it[i] = it[2*i] + it[2*i+1];
for(int i = 0; i < n; ++i) {
if(it[l+i] == 0) continue;
int s = i;
deque<int>& td = (ss[i] < 0 ? rsl : lsl)[abs(ss[i])];
while(it[l+td.front()] == 0) td.pop_front();
int t = td.front();
pset(s, 0);
pset(t, 0);
D(query(s, t));
ret += query(s, t);
for(int i = l; i < l+n; ++i) {
cerr << it[i] << ' ';
}
cerr << '\n';
if(ss[i] > 0) ret += 1;
}
return ret;
}
