#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#if dremix
#define p(x) cerr<<#x<<" = "<<x<<endl;
#define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
#define pp(x) cerr<<#x<<" = ("<<x.F<<" , "<<x.S<<")"<<endl;
#define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
#define ppv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u.F<<"-"<<u.S<<", ";cerr<<"}"<<endl;
#else
#define p(x)
#define p2(x,y)
#define pp(x)
#define pv(x)
#define ppv(x)
#endif
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int maxp = 22;
const ld EPS = 1e-18;
const ll INF = 1e18;
const int MOD = 1e9+7;
const int N = 2e5+1;
template<typename T>
struct SEGTREE{
struct node{
T val; // for adding more stuff
node() : val(0) {}
node(T _val) : val(_val) {}
};
vector<node> seg;
int N;
void init(int n){
N = n;
seg.assign(4*n,node());
}
node merge(node x, node y){
node res;
res.val = x.val + y.val;
return res;
}
void build(int s, int e, int idx, T arr[]){
if(s == e){
seg[idx] = node(arr[s]);
return;
}
int mid = (s+e)/2;
build(s,mid,idx*2,arr);
build(mid+1,e,idx*2+1,arr);
seg[idx] = merge(seg[idx*2],seg[idx*2+1]);
}
// supports 1-indexing
void build(T arr[]){
build(1,N,1,arr);
}
void update(int s, int e, int idx, int k, T val){
if(s==e && s==k){
seg[idx].val += val;
return;
}
if(s>k || e<k)
return;
int mid = (s+e)/2;
update(s,mid,idx*2,k,val);
update(mid+1,e,idx*2+1,k,val);
seg[idx] = merge(seg[idx*2],seg[idx*2+1]);
}
// arr[k] += val
void update(int k, T val){
update(1,N,1,k,val);
}
node query(int s, int e, int idx, int qs, int qe){
if(qs<=s && e<=qe)
return seg[idx];
if(s>qe || e<qs)
return node();
int mid = (s+e)/2;
return merge(query(s,mid,idx*2,qs,qe),query(mid+1,e,idx*2+1,qs,qe));
}
T query(int l, int r){
return query(1,N,1,l,r).val;
}
};
long long count_swaps(vector<int> s) {
int i,n = s.size();
int arr[n+1];
for(i=1;i<=n;i++)arr[i]=1;
SEGTREE<int> seg;
seg.init(n);
seg.build(arr);
vector<set<int> > l(n+1);
vector<set<int> > r(n+1);
ll ans = 0;
for(i=0;i<n;i++){
if(s[i]<0)l[-s[i]].insert(i+1);
else r[s[i]].insert(i+1);
}
for(i=1;i<=n/2;i++){
pv(l[i])
pv(r[i])
}
for(i=0;i<n;i++){
if(seg.query(i+1,i+1)==0)continue;
for(int j=1;j<=n/2;j++){
pv(l[j])
pv(r[j])
}
if(s[i]<0){
int nxt = *(r[-s[i]].begin());
ans += seg.query(1,nxt) - 2;
p2(nxt,ans)
seg.update(i+1,-1);
seg.update(nxt,-1);
r[-s[i]].erase(nxt);
l[-s[i]].erase(i+1);
}
else{
int nxt = *(l[s[i]].begin());
ans += seg.query(1,nxt) - 1;
p2(nxt,ans)
seg.update(i+1,-1);
seg.update(nxt,-1);
r[s[i]].erase(i+1);
l[s[i]].erase(nxt);
}
}
return ans;
}
