#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int maxs=2*maxn;
int n;
int tree[4*maxs];
map<int,deque<int>>idx;
int used[maxs];
void build_tree(int curr,int l,int r)
{
if(l==r)
{
tree[curr]=1;
return;
}
int mid=(l+r)/2;
build_tree(2*curr,l,mid);
build_tree(2*curr+1,mid+1,r);
tree[curr]=tree[2*curr]+tree[2*curr+1];
}
void update(int curr,int l,int r,int pos)
{
if(l==r)
{
tree[curr]=0;
return;
}
int mid=(l+r)/2;
if(pos<=mid)
update(2*curr,l,mid,pos);
else
update(2*curr+1,mid+1,r,pos);
tree[curr]=tree[2*curr]+tree[2*curr+1];
}
int query(int curr,int l,int r,int ql,int qr)
{
if(ql>r or qr<l or l>r)
return 0;
if(ql<=l && r<=qr)
return tree[curr];
int mid=(l+r)/2;
return query(2*curr,l,mid,ql,qr)+query(2*curr+1,mid+1,r,ql,qr);
}
ll solve(vector<int> & s)
{
ll ans=0;
for(int i=0;i<n;i++)
{
if(used[i])
continue;
idx[s[i]].pop_front();
while(!idx[-s[i]].empty() && used[(idx[-s[i]].front())])
idx[-s[i]].pop_front();
int j=idx[-s[i]].front();
idx[-s[i]].pop_front();
int cnt=query(1,0,n-1,i+1,j-1);
ans+=cnt;
update(1,0,n-1,i);
update(1,0,n-1,j);
used[i]=1; used[j]=1;
if(s[i]>0)
ans++;
}
return ans;
}
long long count_swaps(std::vector<int> S)
{
n=S.size();
for(int i=0;i<n;i++)
{
idx[(S[i])].push_back(i);
}
build_tree(1,0,n-1);
return solve(S);
}
