#include "shoes.h"
#include <queue>
#include <cassert>
#define pii pair <int, int>
using namespace std;
const int NMAX = 1e5 + 10;
namespace AIB{
int n;
int aib[NMAX + 1];
void init(int _n){
n = _n;
for(int i = 0; i <= n; i++){
aib[i] = 0;
}
}
int lsb(int x){
return x & -x;
}
void update(int pos, int val){
pos += 1;
for(int i = pos; i <= n; i += lsb(i)){
aib[i] += val;
}
}
int query(int pos){
pos += 1;
int ans = 0;
for(int i = pos; i >= 1; i -= lsb(i)){
ans += aib[i];
}
return ans;
}
}
vector <int> pos[NMAX + 1];
int par[NMAX + 1];
bool viz[NMAX + 1];
long long count_swaps(vector<int> s){
int n = (int)s.size();
for(int i = 0; i < n; i++){
pos[(s[i] < 0 ? -s[i] : s[i])].push_back(i);
}
for(int col = 1; col <= n; col++){
queue <pii> St;
for(int j = 0; j < (int)pos[col].size(); j++){
int i = pos[col][j];
if(!St.empty() && St.front().first == -s[i]){
par[i] = St.front().second;
par[St.front().second] = i;
St.pop();
}else{
St.push({s[i], i});
}
}
}
AIB::init(n);
for(int i = 0; i < n; i++){
AIB::update(i, +1);
}
long long ans = 0;
for(int i = 0; i < n; i++){
if(!viz[i]){
viz[i] = viz[par[i]] = true;
AIB::update(i, -1);
AIB::update(par[i], -1);
ans += AIB::query(par[i]) - AIB::query(i) + (s[i] > s[par[i]]);
}
}
return ans;
}
