#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll>st,lazy;
ll n;
void prop(ll idx,ll l,ll r){
//if(l==4 && r==7)cout<<"y"<<endl;
if(l!=r){
lazy[2*idx+1]+=lazy[idx];
lazy[2*idx+2]+=lazy[idx];
}
st[idx]+=lazy[idx];
lazy[idx]=0;
}
void update(ll idx,ll l,ll r,ll posl,ll posr,ll val){
prop(idx,l,r);
if(l>posr || r<posl)return;
//cout<<idx<<" "<<l<<" k"<<r<<endl;
if(l>=posl && r<=posr){
lazy[idx]+=val;
prop(idx,l,r);
}
else{
ll mid=(l+r)/2;
update(2*idx+1,l,mid,posl,posr,val);
update(2*idx+2,mid+1,r,posl,posr,val);
st[idx]=max(st[2*idx+1],st[2*idx+2]);
}
}
ll query(ll idx,ll l,ll r,ll posl,ll posr){
prop(idx, l, r);
if(l >= posl && r <= posr)
return st[idx];
else if(l > posr || r < posl)
return 0;
else {
ll mid = (l + r) / 2;
return max(query(2 * idx+1, l, mid, posl, posr) , query(2 * idx + 2, mid + 1, r, posl, posr));
}
}
ll count_swaps(vector<int> s) {
n=s.size();
st=lazy=vector<ll>(4*n+1);
deque<ll>pos[2][n+1];
for(ll q=0;q<s.size();q++){
if(s[q]<0){
pos[0][-s[q]].push_back(q);
}
else{
pos[1][s[q]].push_back(q);
}
update(0,0,n,q,q,q);
}
ll ans=0;
bool udh[n+1];
memset(udh,false,sizeof udh);
ll idx=0;
//cout<<query(0,0,n,4,4)<<endl;
for(ll q=0;q<s.size();q++){
if(udh[q])continue;
if(s[q]<0){
ll hah=pos[1][abs(s[q])].front();
pos[0][abs(s[q])].pop_front();
pos[1][abs(s[q])].pop_front();
udh[hah]=true;
ll brp=query(0,0,n,hah,hah);
ans+=brp-idx;
ans--;
update(0,0,n,0,hah,1);
//cout<<hah<<" "<<q<<" "<<brp<<endl;
}
else{
ll hah=pos[0][s[q]].front();
pos[0][s[q]].pop_front();
pos[1][s[q]].pop_front();
udh[hah]=true;
ll brp=query(0,0,n,hah,hah);
ans+=brp-idx;
ans--;
update(0,0,n,0,hah,1);
ans++;
//cout<<hah<<" "<<q<<" "<<brp<<endl;
}
idx+=2;
udh[q]=true;
// cout<<ans<<" "<<query(0,0,n,5,5)<<endl;
}
return ans;
}
