#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
long long n;
map<long long,deque<long long>> mp;
vector<long long> seg(1000000,0);
void update_tree(int pos,int val,int l,int r,int pos_tree)
{
if(pos<l || r<pos || l>r)
{
return;
}
if(pos==l && pos==r)
{
seg[pos_tree]=val;
return;
}
update_tree(pos,val,l,(l+r)/2,pos_tree*2);
update_tree(pos,val,(l+r)/2+1,r,pos_tree*2+1);
seg[pos_tree]=seg[pos_tree*2]+seg[pos_tree*2+1];
}
int sum_tree(int ql,int qr,int l,int r,int pos_tree)
{
if(r<ql || qr<l)
{
return 0;
}
if(ql<=l && r<=qr)
{
return seg[pos_tree];
}
return sum_tree(ql,qr,l,(l+r)/2,pos_tree*2)+sum_tree(ql,qr,(l+r)/2+1,r,pos_tree*2+1);
}
long long count_swaps(vector<int> s)
{
n=s.size();
long long ans=0;
long long LL=0,RR=n-1;
for(int i=0;i<n;i++)
{
mp[s[i]].push_back(i);
}
while(LL<RR)
{
if(s[LL]!=0)
{
long long tmp=0;
long long L=LL+1;
long long R=mp[-s[LL]].front();
mp[s[LL]].pop_front();
mp[-s[LL]].pop_front();
for(int i=L;i<=R;i++)
{
if(s[i]==0)
{
tmp++;
}
}
// cout<<tmp<<" ";
tmp=sum_tree(L,R,0,n-1,1);
ans=ans+R-L-tmp;
// cout<<tmp<<"\n";
if(s[R]<0)
{
ans++;
}
s[R]=0;
s[LL]=0;
update_tree(R,1,0,n-1,1);
update_tree(LL,1,0,n-1,1);
}
if(s[RR]!=0)
{
long long tmp=0;
long long L=mp[-s[RR]].back();
long long R=RR-1;
mp[-s[RR]].pop_back();
mp[s[RR]].pop_back();
for(int i=L;i<=R;i++)
{
if(s[i]==0)
{
tmp++;
}
}
// cout<<tmp<<" ";
tmp=sum_tree(L,R,0,n-1,1);
ans=ans+R-L-tmp;
// cout<<tmp<<"\n";
if(s[L]>0)
{
ans++;
}
s[L]=0;
s[RR]=0;
update_tree(L,1,0,n-1,1);
update_tree(RR,1,0,n-1,1);
}
// cout<<LL<<RR;
LL++;
RR--;
}
return ans;
}
