#include <bits/stdc++.h>
#include "shoes.h"
#define ll long long
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define fi first
#define se second
using namespace std;
const int MAXN = 2e5+5 ;
vector<int> posR[MAXN],posL[MAXN] ;
int ft[MAXN] , n ;
int lsO(int x){
return x&(-x);
}
int sum(int x ){
if( x<=0 )return 0 ;
int s = 0;
for(int i = x; i > 0 ; i -= lsO(i) )
s += ft[i];
return s ;
}
int pref(int x){
return sum(2*n+1)-sum(x-1);
}
void update (int x ){
if(x <= 0 )return ;
for(int i = x ; i <= 2*n+1 ; i+= lsO(i))
ft[i]++;
}
long long count_swaps(std::vector<int> s) {
ll ans = 0;
n = sz(s)/2 ;
for(int i=0;i<sz(s);i++ ){
int a = s[i] ;
if( a > 0 )posR[a].pb(i+1);
else posL[-a].pb(i+1) ;
}
priority_queue<pi,vector<pi>,greater<pi>> q;
for(int i = 1 ; i <= n ; i++ ){
if( posR[i].empty() )continue ;
reverse(all(posR[i]));
reverse(all(posL[i]));
q.push({posR[i].back() + posL[i].back(),i});
}
int toadd = 0;
for(int i = 1 ; i <= n ; i++ ){
int l = i * 2 - 1 , r = i*2 ;
int j = q.top().se ;
int x = posL[j].back() , y = posR[j].back();
// x += pref(x) ;
update (x-1);
// y += pref(y);
update(y-1);
toadd = x + y - l - r ;
posR[j].pop_back();
posL[j].pop_back();
q.pop();
// cout << x << " " << y << " " << j << " " << toadd<< endl;
// if( !posL[j].empty() )
// q.push({posR[j].back() + posL[j].back(),j});
while ( !q.empty())q.pop() ;
for(int j = 1 ; j <= n ; j++ ){
if( posR[j].empty() )continue ;
for(int &x : posL[j])x+=pref(x);
for(int &x : posR[j])x+=pref(x);
sort(all(posR[j]));
sort(all(posL[j]));
reverse(all(posR[j]));
reverse(all(posL[j]));
q.push({posL[i].back()+posR[i].back(),j});
}
ans += 1LL*toadd ;
}
return ans;
}
// int main() {
// int n;
// assert(1 == scanf("%d", &n));
// vector<int> S(2 * n);
// for (int i = 0; i < 2 * n; i++)
// assert(1 == scanf("%d", &S[i]));
// fclose(stdin);
// long long result = count_swaps(S);
// printf("%lld\n", result);
// fclose(stdout);
// return 0;
// }
