#include "shoes.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
#define f0r(i,n) for(int i = 0; i<n; i++)
#define pb push_back
#define vi vector<int>
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<'\n';
#define dout(x) cout<<x<<' '<<#x<<'\n';
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> os;
int count_swaps(std::vector<signed> s) {
int n = s.size();
if(n == 2){
if(s[0] < 0)return 0;
else return 1;
}
else{
/*
vi a;
vi b;
vi c; vi d;
f0r(i, n){
if(s[i] < 0){
a.pb(s[i]);
c.pb(i);
}
else{
b.pb(s[i]);
d.pb(i);
}
}
int ans = 4e18;
vi loc;
f0r(i, n/2)loc.pb(i);
vector<vi> opti;
do{
vi loc2;
f0r(i, n/2)loc2.pb(i);
do{
bool ok = 1;
for(int i = 0; i<n/2; i++){
if(a[loc[i]] != -b[loc2[i]]){
ok = 0;
}
}
if(ok){
vi locc;
f0r(i, n/2){
locc.pb(c[loc[i]]);
locc.pb(d[loc2[i]]);
}
os ay;
ay.insert(locc[n-1]);
int cur = 0;
for(int i = n-2; i>=0; i--){
cur += ay.order_of_key(locc[i]);
ay.insert(locc[i]);
}
if(cur < ans){
ans = cur;
vi thing;
f0r(i, n/2){
thing.pb(-a[loc[i]]);
}
opti = {thing};
}
else if(cur == ans){
ans = cur;
vi thing;
f0r(i, n/2){
thing.pb(-a[loc[i]]);
}
opti.pb(thing);
}
}
}while(next_permutation(loc2.begin(), loc2.end()));
}while(next_permutation(loc.begin(), loc.end()));
dout(ans);
for(auto u : opti){
vout(u);
}
int a1 = ans;
*/
vi rs;
vi lok(n);
vector<set<int>> lef(n + 1);
vector<set<int>>rig(n + 1);
int cur = 0;
f0r(i, n){
if(s[i] > 0){
if(lef[s[i]].size() > 0){
lok[(*lef[s[i]].begin())] = cur;
lef[s[i]].erase(lef[s[i]].begin());
lok[i] = cur + 1;
cur += 2;
}
else{
rig[s[i]].insert(i);
}
}
else{
if(rig[-s[i]].size() > 0){
lok[(*rig[-s[i]].begin())] = cur + 1;
rig[-s[i]].erase(rig[-s[i]].begin());
lok[i] = cur;
cur += 2;
}
else{
lef[-s[i]].insert(i);
}
}
}
//how many ppl after me are less than me
// vout(lok);
os aa;
aa.insert(lok[n-1]);
int ans = 0;
for(int i = n-2; i>=0; i--){
ans += aa.order_of_key(lok[i]);
aa.insert(lok[i]);
}
/*
dout(ans);
int a2 = ans;
if(a1 != a2){
vout(s);
}
*/
return ans;
}
return 1;
}
