#include <bits/stdc++.h>
#include <cstdio>
#include <cassert>
#include "shoes.h"
#define ll int
#define pb push_back
#define all(x) (x).begin(), (x).end()
using namespace std;
ll t[4*200010];
ll tadd[4*200010];
void push(ll v,ll l,ll r)
{
if(tadd[v]!=0)
{
t[v]+=tadd[v];
if(l!=r)
{
tadd[v*2]+=tadd[v];
tadd[v*2+1]+=tadd[v];
}
tadd[v]=0;
}
}
void build(ll v,ll l,ll r)
{
if(l==r)
{
t[v]=l;
return ;
}
ll mid=l+(r-l)/2;
build(v*2,l,mid);
build(v*2+1,mid+1,r);
t[v]=max(t[v*2],t[v*2+1]);
}
void update1(ll v,ll l,ll r,ll nac,ll konec,ll x)
{
push(v,l,r);
if(l>konec || r<nac)return ;
if(l>=nac && r<=konec)
{
tadd[v]+=x;
push(v,l,r);
return ;
}
ll mid=l+(r-l)/2;
update1(v*2,l,mid,nac,konec,x);
update1(v*2+1,mid+1,r,nac,konec,x);
t[v]=max(t[v*2],t[v*2+1]);
}
void update2(ll v,ll l,ll r,ll pos,ll x)
{
push(v,l,r);
if(l==r)
{
t[v]=x;
return ;
}
ll mid=l+(r-l)/2;
if(pos<=mid)update2(v*2,l,mid,pos,x);
else update2(v*2+1,mid+1,r,pos,x);
t[v]=max(t[v*2],t[v*2+1]);
}
ll query(ll v,ll l,ll r,ll pos)
{
push(v,l,r);
if(l==r)
{
return t[v];
}
ll mid=l+(r-l)/2;
if(pos<=mid)return query(v*2,l,mid,pos);
else return query(v*2+1,mid+1,r,pos);
}
vector<ll>leftt[200010];
vector<ll>rightt[200010];
ll used[200010];
long long count_swaps(vector<int>massiv)
{
ll n=(ll)massiv.size();
set<ll>nuj;
build(1,1,n);
for(ll i=0;i<n;i++)
{
if(massiv[i]<0)leftt[abs(massiv[i])].pb(i+1);
else rightt[massiv[i]].pb(i+1);
nuj.insert(massiv[i]);
}
for(auto i:nuj)
{
if(i<0)reverse(all(leftt[abs(i)]));
else reverse(all(rightt[i]));
}
long long ans=0;
for(ll i=0;i<n;i++)
{
if(used[i+1])continue;
if(massiv[i]>0)
{
rightt[massiv[i]].pop_back();
ll pos=leftt[massiv[i]].back();
used[pos]=1;
used[i+1]=1;
leftt[massiv[i]].pop_back();
ll pos1=query(1,1,n,pos);
ll pos2=query(1,1,n,i+1);
ans+=pos1-pos2;
update1(1,1,n,i+2,pos-1,1);
update2(1,1,n,i+1,pos2+1);
update2(1,1,n,pos,pos2);
}
else if(massiv[i]<0)
{
leftt[-massiv[i]].pop_back();
ll pos=rightt[-massiv[i]].back();
used[pos]=1;
used[i+1]=1;
rightt[-massiv[i]].pop_back();
ll pos1=query(1,1,n,pos);
ll pos2=query(1,1,n,i+1);
ans+=((pos1-pos2)-1);
update1(1,1,n,i+2,pos-1,1);
update2(1,1,n,pos,pos2+1);
}
}
return ans;
}
