#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;
//Slozenost O(log n)
template<class T, int size>
struct fenwick {
T a[size];
/* precondition: pos > 0 */
void add(int pos, const T& val) {
while (pos < size) {
a[pos] += val;
pos += pos & -pos;
}
}
T sum(int pos) {
T ret = T();
while (pos > 0) {
ret += a[pos];
pos -= pos & -pos;
}
return ret;
}
T sum(int l, int r){
if (l>r) return 0;
if (l == 1)
return sum(r);
return sum(r)-sum(l-1);
}
};
fenwick<int,131072*2> drvo;
ll count_swaps(vi a){
int n = a.size();
queue<int> s[n+2], t[n+2];
vi pos(n+1,-1);
for (int i = 0; i < n; ++i){
if (a[i]>0){
int x = a[i];
if (t[x].empty()){
s[x].push(i);
continue;
}
pos[i] = t[x].front();
pos[pos[i]] = i;
t[x].pop();
} else {
int x = -a[i];
if (s[x].empty()){
t[x].push(i);
continue;
}
pos[i] = s[x].front();
pos[pos[i]] = i;
s[x].pop();
}
}
vi vis(n+1, 0);
ll sol = 0;
for (int i = 1; i <= n; ++i)
drvo.add(i,1);
for (int i = 0; i < n; ++i){
if (vis[i]) continue;
sol += drvo.sum(i+2,pos[i]);
if (a[i] > 0)
++sol;
drvo.add(i+1,-1);
drvo.add(pos[i]+1,-1);
vis[i] = vis[pos[i]] = 1;
}
return sol;
}
