#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <map>
#include <deque>
using namespace std;
struct A
{
int l,r;
int nxl,nxr;
int how;
}Node[1000005];
int a[200005];
int b[200005];
int now=1;
map < int , deque < int > > all1;
map < int , deque < int > > all2;
void build(int l,int r,int here)
{
Node[here].l=l;
Node[here].r=r;
Node[here].how=0;
if(l==r) return;
Node[here].nxl=now++;
Node[here].nxr=now++;
build(l,(l+r)/2,Node[here].nxl);
build((l+r)/2+1,r,Node[here].nxr);
}
void change(int l,int r,int here)
{
if(l==Node[here].l&&r==Node[here].r)
{
Node[here].how++;
return;
}
if(r<=(Node[here].l+Node[here].r)/2) change(l,r,Node[here].nxl);
else if(l>(Node[here].l+Node[here].r)/2) change(l,r,Node[here].nxr);
else
{
change(l,(Node[here].l+Node[here].r)/2,Node[here].nxl);
change((Node[here].l+Node[here].r)/2+1,r,Node[here].nxr);
}
}
int Find(int where,int here)
{
//printf("a %d\n",here);
if(where==Node[here].l&&where==Node[here].r) return Node[here].how;
if(where<=(Node[here].l+Node[here].r)/2) return Find(where,Node[here].nxl)+Node[here].how;
else if(where>(Node[here].l+Node[here].r)/2) return Find(where,Node[here].nxr)+Node[here].how;
}
long long count_swaps(std::vector<int> S)
{
long long ans1=0,small,what,t,a,b;
int i,j,k,N=S.size(),x=0;
build(0,N-1,0);
for(i=0;i<N/2;i++) if(!(S[i]<0&&0-S[i]==S[i+N/2])) break;
if(i==N/2) return ((long long) N/2)*((long long) N/2-1)/2;
for(i=0;i<N;i++)
{
if(x&&abs(S[i])!=x) x=100000000;
else if(x==0) x=abs(S[i]);
if(S[i]<0) all1[0-S[i]].push_back(i);
else all2[S[i]].push_back(i);
}
//printf("aa");
if(x!=100000000)
{
for(i=0;i<N/2;i++)
{
small=1000000000;
a=all1[x].front()+Find(all1[x].front(),0);
b=all2[x].front()+Find(all2[x].front(),0);
t=a+b;
if(a>b) t++;
if(t<small)
{
small=t;
what=x;
}
//printf("%lld %lld\n",what,small);
ans1+=(small-i*2-i*2-1);
change(0,all1[what].front(),0);
change(0,all2[what].front(),0);
all1[what].pop_front();
all2[what].pop_front();
if(all1[what].empty())
{
all1.erase(what);
all2.erase(what);
}
}
}
else
{
for(i=0;i<N/2;i++)
{
small=1000000000;
for(auto j:all1)
{
//printf("%d %d %d\n",j.first,all1[j.first].front(),all2[j.first].front());
a=all1[j.first].front()+Find(all1[j.first].front(),0);
b=all2[j.first].front()+Find(all2[j.first].front(),0);
t=a+b;
if(a>b) t++;
if(t<small)
{
small=t;
what=j.first;
}
}
//printf("%lld %lld\n",what,small);
ans1+=(small-i*2-i*2-1);
change(0,all1[what].front(),0);
change(0,all2[what].front(),0);
all1[what].pop_front();
all2[what].pop_front();
if(all1[what].empty())
{
all1.erase(what);
all2.erase(what);
}
}
}
return ans1;
}
