#include <bits/stdc++.h>
#include <shoes.h>
using namespace std;
using ll = long long;
template<class T> struct Seg {
const T sta = 0;
T comb(T a, T b){
return a + b;
}
int n; vector<T> seg;
void init(int nn){
n = nn;
seg.assign(3*n, sta);
}
void pull(int q){
seg[q] = comb(seg[2*q], seg[2*q+1]);
}
void update(int q, T val){
seg[q+=n] += val; for(q/=2; q!=0;q/=2) pull(q);
}
T query(int l, int r){
T ri = sta, la = sta;
for(l += n, r+= n+1; l < r; l/=2, r/=2){
if(l&1) ri = comb(ri, seg[l++]);
if(r&1) la = comb(seg[--r], la);
}
return comb(ri, la);
}
};
ll count_swaps(vector<int> S){
int n = S.size()/2;
// cerr << "N " << n << endl;
Seg<int> seg;
map<int, vector<int>> mp;
vector<int> seen(2 * n, 0);
for(int i=0; i < 2*n; i++){
mp[S[i]].push_back(i);
}
for(auto&z : mp){
sort(z.second.begin(), z.second.end(), greater<int>());
// cerr << z.first << " ";
// for(auto& v : z.second){
// cerr << v << " " ;
// }
// cerr << endl;
}
ll ans = 0;
seg.init(2 * n);
for(int i = 0; i < 2 * n; i++){
if(!seen[i]){
int x = mp[-S[i]].back();
seen[x] = 1;
seen[i] = 1;
mp[-S[i]].pop_back();
mp[S[i]].pop_back();
int pos1 = i + seg.query(0, i);
int pos2 = x + seg.query(0, x);
if(((pos2 < pos1) && S[i] < 0) || (S[i] > 0 && pos1 < pos2)){
ans++;
}
// cerr << "POS1 " << i << " POS2 " << x << endl;
ans += abs(pos2 - pos1 - 1);
seg.update(i + 1, 1);
seg.update(x, -1);
}
}
return ans;
}
// int main(){
// vector<int> arr = {2, 1, -1, -2};
// cout << count_swaps(arr) << endl;
// }
