#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define tiii tuple<int,int,int>
#define tiiii tuple<int,int,int,int>
#define pb push_back
#define eb emplace_back
#define emp emplace
#define mkp make_pair
#define mkt make_tuple
#define vctr vector
#define arr array
#define all(x) x.begin(), x.end()
#define amin(a,b) a = min(a,b)
#define amax(a,b) a = max(a,b)
#define brick(x) cout << #x << " = " << (x) << " | "
#define dbg(x) cout << #x << " = " << (x) << '\n'
#define vdbg(a) cout << #a << " = "; for(auto _x : a)cout << _x << ' '; cout << '\n'
#define adbg(a,n) cout << #a << " = "; for(int _i = 1; _i <= n; ++_i)cout << a[_i] << ' '; cout << '\n'
#define adbg0(a,n) cout << #a << " = "; for(int _i = 0; _i < n; ++_i)cout << a[_i] << ' '; cout << '\n'
mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));
int uid(int a, int b) { return uniform_int_distribution<int>(a,b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a,b)(rng); }
const int MOD = 1e9+7; // 998244353;
int a[100005];
vctr<int> b[2][100005];
struct FenwickTree {
using T = int;
T tree[100005];
int n = -1;
void init(int _n) {
n = _n;
fill(tree+1,tree+n+1,0);
}
void upd(int x, T val) {
assert(n > 0);
for (int i = x; i <= n; i += i&-i) {
tree[i] += val;
}
return;
}
T qry(int x, int y) {
assert(n > 0);
if (x > 1)return qry(1,y)-qry(1,x-1);
T res = 0;
for (int i = y; i > 0; i -= i&-i) {
res += tree[i];
}
return res;
}
} tree;
ll count_swaps(vctr<int> _v) {
int n = _v.size();
for (int i = 1; i <= n; ++i) {
a[i] = _v[i-1];
}
for (int i = 1; i <= n; ++i) {
b[a[i] > 0][abs(a[i])].pb(i);
}
vctr<pii> v;
int ans = 0;
for (int i = 1; i <= n/2; ++i) {
int k = b[0][i].size();
for (int j = 0; j < k; ++j) {
int l = b[0][i][j];
int r = b[1][i][j];
if (r < l) {
++ans;
swap(l,r);
}
v.eb(r,l);
}
}
sort(all(v));
tree.init(2*n);
for (auto [r,l] : v) {
ans += tree.qry(l,r);
tree.upd(l,1);
tree.upd(r,1);
}
return ans;
}
