#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define pb push_back
const int maxn = 1<<19;
int seg[2 * maxn];
int op(int a,int b){
return a + b;
}
void update(int i,int v){
i+=maxn;
seg[i]=v;
for(i /= 2;i > 0;i /= 2){
seg[i] = op(seg[i * 2], seg[i * 2 +1 ]);
}
}
int que(int l,int r,int lo = 0,int mx = maxn - 1,int x = 1){
if (l <= lo && mx <= r)return seg[x];
if (r < lo || mx < l)return 0;
int mid= (lo + mx) / 2;
int xl = x * 2,xr = xl+1;
int tl = que(l,r,lo,mid,xl);
int tr =que(l,r,mid+1,mx,xr);
return op(tl,tr);
}
long long count_swaps(vector <int> s){
vector <int> nm(maxn, -1);
vector <vector <int>> ne(maxn);
vector <vector <int>> pos(maxn);
int n = s.size();
for(int i = 0;i < n;i++){
if(s[i] > 0){
pos[s[i]].push_back(i);
}
else{
ne[-s[i]].push_back(i);
}
}
vector <bool> vis(maxn, 0);
for(int i = n - 1;i >= 0;i--){
if(vis[i])continue;
vis[i] = 1;
if(s[i] > 0){
nm[i] = ne[s[i]].back();
ne[s[i]].pop_back();
}
else{
nm[i] = pos[-s[i]].back();
pos[-s[i]].pop_back();
}
vis[nm[i]] = true;
}
fill(all(vis), false);
for(int i = 0;i < n;i++){
update(i, 1);
}
int ans = 0;
for(int i = n - 1;i >= 0;i--){
if(vis[i])continue ;
vis[i] = vis[nm[i]] = true;
if(s[i] > 0){
if(nm[i] != i - 1)
ans += que(nm[i] + 1, i - 1);
update(nm[i], 0);
}
else{
if(nm[i] != i - 1)
ans += que(nm[i] + 1, i - 1);
update(nm[i], 0);
}
if(s[i] < 0)ans++;
//cout<<ans<<' ';
}
return ans;
}
