#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
struct SegTree {
vector<int> tree;
SegTree(int n) {
tree.assign(4*n, 0);
}
void query(int p, int l, int r, int i, int x) {
if (l>i || r < i) return;
if (l==r) {
tree[p] = x;
return;
}
int m = (l+r)/2;
query(2*p, l, m, i, x);
query(2*p+1, m+1, r, i, x);
tree[p] = tree[2*p] + tree[2*p+1];
}
int kth(int p, int l, int r, int k) {
if (l==r) return l;
int m = (l+r)/2;
//cout << l << " " << r << " " << m << " " << k << " " << tree[2*p] << endl;
if (tree[2*p] >= k) {
return kth(2*p, l, m, k);
}
else {
return kth(2*p+1, m+1, r, k-tree[2*p]);
}
}
int rsq(int p, int l, int r, int i, int j) {
if (l>j || r<i) return 0;
if (i<=l && r<=j) return tree[p];
int m = (l+r)/2;
return rsq(2*p, l, m, i, j) + rsq(2*p+1, m+1, r, i, j);
}
};
long long count_swaps(vector<int> s) {
int n = s.size()/2;
ll ans=0;
SegTree st(2*n);
for (int i=0; i<2*n; i++) {
st.query(1, 0, 2*n-1, i, 1);
}
int ordered = 2*n;
set<pii> se;
for (int i=0; i<2*n; i++) {
se.insert({s[i], i});
}
while (ordered>0) {
//cout << ordered << endl;
int i1 = st.kth(1, 0, 2*n-1, ordered);
auto it = se.upper_bound({-s[i1], 3*n});
it--;
int i2 = it->second; //indice mas cercano con valor bueno jiju
st.query(1, 0, 2*n-1, i1, 0);
st.query(1, 0, 2*n-1, i2, 0);
//cout << i1 << " " << i2 << " " << s[i1] << " " << s[i2] << " " << st.rsq(1, 0, 2*n-1, i2, i1) << endl;
ans += st.rsq(1, 0, 2*n-1, i2, i1);
if (s[i1] < 0) ans++;
se.erase({s[i1], i1});
se.erase({s[i2], i2});
ordered-=2;
}
return ans;
}
//3
//-2 2 2 -2 -2 2
