#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pi pair<int,int>
const int maxn = 2e5 + 5;
struct SegTree{
int st[maxn * 4];
int sz;
void init(){
sz = maxn;
memset(st, 0, sizeof st);
}
void upd(int n, int l, int r, int ind, int val){
if(l == r){
st[n] = val;
return;
}
int mid = (l + r)/2;
if( ind <= mid)
upd(2* n + 1, l, mid, ind, val);
else
upd(2*n +2, mid +1, r,ind, val);
st[n] = st[2*n+1] + st[2* n + 2];
}
void insert(int val ){
upd(0,1, sz, val+1, 1);
}
void erase(int val){
upd(0,1, sz, val+1, 0);
}
int qry(int n, int l, int r, int s, int e){
if( e < s) return 0;
if( s <= l and e >= r) return st[n];
int ans = 0;
int mid = (l + r) /2;
if( s <= mid)
ans+=qry(2 * n + 1, l ,mid, s, e);
if( e > mid)
ans += qry(2* n+2, mid + 1, r, s,e);
return ans;
}
int getind(int val){
return qry(0, 1,sz,1, val);
}
};
SegTree shoes;
long long count_swaps(vector<int> s) {
ll ans = 1e18;
int n = s.size();
vector<pi> lefts(n/2);
int cntleft = 0;
vector<pair<int, pi>> sortlefts(n/2);
vector<queue<int>> rightinds(n);
shoes.init();
for(int i =0; i<n ;i++){
shoes.insert(i);
if(s[i] > 0){
rightinds[s[i]].push(i);
}
}
for(int i =0; i<n; i++){
if(s[i] < 0){
int firstright = rightinds[-s[i]].front();
rightinds[-s[i]].pop();
lefts[cntleft++] = {i, firstright};
sortlefts[cntleft - 1] = {i+firstright, {i, firstright}};
}
}
sort(sortlefts.begin(), sortlefts.end());
for(int i =0; i<n/2; i++){
lefts[i] = sortlefts[i].second;
}
ll posans = 0;
vector<int> inds(n);
for(int i =0; i<n ;i++) inds[i] = i;
//for(int i =0; i<n/ 2; i++) cout << lefts[i]<<", "; cout <<endl;
int l = 0;
for(pi shoe : lefts){
//get first availabe
int leftind = shoe.first;
int rightind = shoe.second;
//cout <<endl;
int newleftind = 2 * l + shoes.getind(leftind);
ll dist1 = abs(newleftind - 2 * l);
shoes.erase(leftind);
int newrightind = 2 * l + 1 + shoes.getind(rightind);
//cout <<leftind<<", "<<rightind<<": "<< newleftind<<", "<<newrightind<<endl;
ll dist2 = abs(newrightind -( 2 * l + 1));
shoes.erase(rightind);
/*for(int ss : shoes){
cout <<ss<<", ";
}
cout <<endl;
*/
//cout << inds[lefts[l]]<<", "<<inds[firstright]<<": ";
//cout << lefts[l]<<", "<<firstright<<": "<<dist1<<", "<<dist2<<endl;
posans += dist1 + dist2;
l++;
}
ans = min(ans, posans);
//cout << posans<<endl<<endl;
return ans;
}
/***********/
