#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
template<typename T>
using vec = vector<T>;
using ll = long long;
using vll = vec<ll>;
using pll = pair<ll,ll>;
#define pb push_back
#define dbg(x) cerr << #x << ": " << x << endl;
void bruh(queue<ll> q) {
while(!q.empty()) {
cerr << q.front() << " ";
q.pop();
}
}
ll conv(ll x) {
if(x < 0) return -x + 100000;
return x;
}
class comp {
public:
bool operator()(pll a, pll b) {
return a.first + a.second > b.first + b.second;
}
};
struct Segtree { // range addition, point query so it doesnt matter lol
ll l, r;
Segtree *lt, *rt;
ll val;
ll lazy;
void combine() {
val = min(lt->val,rt->val);
}
Segtree(ll lf, ll rf, vll &a) {
l = lf, r = rf;
lt = rt = nullptr;
lazy = 0;
if(l == r) {
val = a[l];
return;
}
ll mid = (l+r)>>1;
lt = new Segtree(l,mid,a);
rt = new Segtree(mid+1,r,a);
combine();
}
void propagate() {
if(lazy) {
val += lazy;
if(lt) {
rt->lazy += lazy;
lt->lazy += lazy;
}
lazy = 0;
}
}
ll query(ll ql, ll qr) {
propagate();
if(qr < l or r < ql) return 1e18;
if(ql <= l and r <= qr) return val;
return min(lt->query(ql,qr), rt->query(ql,qr));
}
void update(ll ul, ll ur) {
propagate();
if(ur < l or r < ul) return;
if(ul <= l and r <= ur) {
lazy++;
propagate();
return;
}
lt->update(ul,ur);
rt->update(ul,ur);
combine();
}
};
long long count_swaps(std::vector<int> s) {
ll n = s.size()>>1;
ll out = 0;
priority_queue<pll, vec<pll>, comp> pq;
vec<queue<ll>> dists(200001);
vll sta(2*n+1,0);
for(ll j = 0; j < 2 * n; j++) {
ll shoe = conv(s[j]);
dists[shoe].push(j);
}
for(int i = 0; i <= n; i++) {
while(!dists[i].empty()) {
pq.push({dists[i].front(), dists[i+100000].front()});
dists[i].pop();
dists[i+100000].pop();
}
}
Segtree st(0,2*n-1,sta);
ll mult = 0;
while(!pq.empty()) {
pll temp = pq.top();
pq.pop();
ll x = temp.first;
ll y = temp.second;
ll netX = x + st.query(x,x);
ll netY = y + st.query(y,y);
if(x > y) netX--;
if(netX) st.update(0,x-1);
if(netY) st.update(0,y-1);
out += netX + netY - (2 * mult);
mult += 2;
}
return out;
}
/*
4
2 -2 3 -3 2 -2 3 -3
output: 4
*/
/*
idea: essentially just moving things to the first slot.
greedily, best to move the negative first
*/
