#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define V vector
struct segtree{
private:
struct node{
int sum;
int len;
};
node neutral={0,0};
static node merge(node a,node b){
return{a.sum+b.sum,a.len+b.len};
}
static node modification(node a,int b){
return{a.sum+a.len*b,a.len};
}
static int operation_modifier(int a,int b){
return a+b;
}
public:
int size;
V<node>query;
V<int>operation;
void init(int n) {
size = 1;
while (size < n)size *= 2;
query.assign(2 * size, {0, 1});
operation.assign(2 * size, 0);
}
void build(int x,int lx,int rx){
if(rx-lx==1)
return;
int m=(lx+rx)/2;
build(2*x+1,lx,m);
build(2*x+2,m,rx);
query[x]=merge(query[2*x+1],query[2*x+2]);
}
void build(){
build(0,0,size);
}
void set(int l,int r,int v,int x,int lx,int rx){
if(rx<=l || lx>=r)
return;
if(l<=lx && rx<=r){
operation[x]=operation_modifier(operation[x],v);
query[x]=modification(query[x],v);
return;
}
int m=(lx+rx)/2;
set(l,r,v,2*x+1,lx,m);
set(l,r,v,2*x+2,m,rx);
query[x]=modification(merge(query[2*x+1],query[2*x+2]),operation[x]);
}
void set(int l,int r,int v){
set(l,r,v,0,0,size);
}
node calc(int l,int r,int x,int lx,int rx){
if(rx<=l || lx>=r)
return neutral;
if(l<=lx && rx<=r)
return query[x];
int m=(lx+rx)/2;
node a=calc(l,r,2*x+1,lx,m);
node b=calc(l,r,2*x+2,m,rx);
return modification(merge(a,b),operation[x]);
}
int calc(int l,int r){
return calc(l,r,0,0,size).sum;
}
int get(int i){
return calc(i,i+1);
}
};
long long count_swaps(std::vector<int> s) {
int n=(int)s.size();
segtree tree;
tree.init(n);
tree.build();
map<int,stack<int>>mp;
bool vis[n];
memset(vis,false,sizeof(vis));
for(int i=n-1;i>=0;i--)
mp[s[i]].push(i);
long long c=0;
for(int i=0;i<n;i+=2){
int a;
int ans=-1;
int l=0,r=i-tree.get(i);
while(l<=r){
int m=l+(r-l)/2;
if(m+tree.get(m)==i && !vis[m]){
ans=m;
break;
}
if(m+tree.get(m)>=i)
r=m-1;
else
l=m+1;
}
a=s[ans];
vis[mp[a].top()]=true;
vis[mp[-1*a].top()]=true;
int pos=mp[-1*a].top()+tree.get(mp[-1*a].top());
c+=pos-i-1;
if(a>0)
c++;
tree.set(mp[a].top(),mp[-1*a].top(),1);
mp[-1*a].pop();
mp[a].pop();
}
return c;
}
