#include "shoes.h"
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
#define ll long long
using namespace std;
int n;
vector <int> lazy, seg;
void prop(int l, int r, int x){
if(l != r){
lazy[2*x] += lazy[x];
lazy[2*x + 1] += lazy[x];
}
seg[x] += lazy[x];
lazy[x] = 0;
}
void upd(int l, int r, int tl, int tr, int pos, int val){
prop(l, r, pos);
if(r < tl || tr < l)return;
if(l <= tl && tr <= r){
lazy[pos] += val;
prop(l, r, pos);
}
else{
int mid = (l + r) >> 1;
upd(l, mid, tl, tr, 2*pos, val);
upd(mid + 1, r, tl, tr, 2*pos + 1, val);
seg[pos] = max(seg[2*pos], seg[pos*2 + 1]);
}
}
int query(int l, int r, int tl, int tr, int pos){
prop(l, r, pos);
if(tl <= l && r <= tr)return seg[pos];
if(tr < l || r < tl)return 0;
int mid = (l + r) >> 1;
return max(query(l, mid, tl, tr, 2*pos), query(mid + 1, r, tl, tr, 2*pos + 1));
}
long long count_swaps(vector<int> v) {
n = (int)v.size();
lazy = seg = vector <int> (4*n + 5, 0);
deque <int> dq[2][n + 5];
for(int i = 0 ; i < n ; i++){
if(v[i] < 0)dq[0][-v[i]].pb(i);
else dq[1][v[i]].pb(i);
upd(0, n, i, i, 0, i);
}
ll ans = 0;
bool vis[n + 1];memset(vis, 0, sizeof(vis));
ll idx = 0;
for(int i = 0 ; i < n ; i++){
if(vis[i])continue;
if(v[i] < 0){
ll tmp = dq[1][abs(v[i])].front();
dq[0][abs(v[i])].pop_front();
dq[1][abs(v[i])].pop_front();
vis[tmp] = 1;
ll tot = query(0, n, tmp, tmp, 0);
ans += tot - idx;
ans--;
upd(0, n, 0, tmp, 0, 1);
}
else{
ll tmp = dq[0][abs(v[i])].front();
dq[0][abs(v[i])].pop_front();
dq[1][abs(v[i])].pop_front();
vis[tmp] =1;
ll tot = query(0, n, tmp, tmp, 0);
ans += tot - idx;
ans--;
upd(0, n, 0, tmp, 0, 1);
ans++;
}
idx += 2;
vis[i] = 1;
}
return ans;
}
