#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
int pos[100001];
int lazy[400001];
int tree[400001];
void build(int start,int l,int r)
{
if(l==r)
{
tree[start]=pos[l];
return;
}
int m=(l+r)/2;
build(2*start+1,l,m);
build(2*start+2,m+1,r);
tree[start]=tree[2*start+1]+tree[2*start+2];
}
void update(int start,int i,int j,int l,int r,int val)
{
if(lazy[start]!=0)
{
tree[start]+=(r-l+1)*val;
if(l!=r)
{
lazy[2*start+1]+=lazy[start];
lazy[2*start+2]+=lazy[start];
}
lazy[start]=0;
}
if(l>r || l>j || r<i)return;
if(l>=i && r<=j)
{
tree[start]+=(r-l+1)*val;
if(l!=r)
{
lazy[2*start+1]+=val;
lazy[2*start+2]+=val;
}
return;
}
int m=(l+r)/2;
update(2*start+1,i,j,l,m,val);
update(2*start+2,i,j,m+1,r,val);
tree[start]=tree[2*start+1]+tree[2*start+2];
}
int query(int start,int i,int j,int l,int r)
{
if(lazy[start]!=0)
{
tree[start]+=(r-l+1)*lazy[start];
if(l!=r)
{
lazy[2*start+1]+=lazy[start];
lazy[2*start+2]+=lazy[start];
}
lazy[start]=0;
}
if(l>r || l>j || r<i)return 0;
if(l>=i && r<=j)return tree[start];
int m=(l+r)/2;
int q1=query(2*start+1,i,j,l,m);
int q2=query(2*start+2,i,j,m+1,r);
return q1+q2;
}
long long count_swaps(vector<int> s)
{
long long rez=0;
int n=s.size();
for(int i=0;i<n;i++)
{
pos[i]=i;
}
build(0,0,n-1);
for(int i=0;i<n;i+=2)
{
for(int j=i+1;j<n;j++)
{
int pos1=query(0,i,i,0,n-1);
int pos2=query(0,j,j,0,n-1);
if(abs(s[pos1])==abs(s[pos2]) && s[pos1]*s[pos2]<0)
{
rez+=(pos2-pos1-1);
update(0,0,n-1,pos1+2,pos2,-1);
update(0,0,n-1,pos1+1,pos1+1,(pos2-pos1-1));
if(s[pos2]<0)
{
update(0,0,n-1,pos1+1,pos1+1,-1);
update(0,0,n-1,pos1,pos1,1);
rez++;
}
break;
}
}
}
return rez;
}
