#include "shoes.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
using namespace std;
vector<int> kiri[200005], kanan[200005];
vector<pair<int,int> > swaps;
int tree[4 * 200005];
void upd(int idx, int l, int r, int titik, int val){
if(titik > r || titik < l){
return;
}
if(l == r){
tree[idx] += val;
return;
}
upd(2 * idx, l, (l + r)/2, titik, val);
upd(2 * idx + 1, (l + r)/2 + 1, r, titik, val);
tree[idx] = tree[2 * idx] + tree[2 * idx + 1];
}
int cari(int idx, int l, int r, int kiri, int kanan){
if(kiri > r || kanan < l){
return 0;
}
if(l >= kiri && r <= kanan){
return tree[idx];
}
int satu = cari(2 * idx, l, (l + r)/2, kiri, kanan);
int dua = cari(2 * idx + 1, (l + r)/2 + 1, r, kiri, kanan);
return satu + dua;
}
long long count_swaps(vector<int> s) {
int n = s.size() / 2;
for(int i = 0; i < s.size(); i++){
if(s[i] < 0){
kiri[-s[i]].pb(i + 1);
}else{
kanan[s[i]].pb(i + 1);
}
}
int ans = 0;
for(int i = 1; i < s.size() + 5; i++){
for(int j = 0; j < kiri[i].size(); j++){
int lef = kiri[i][j];
int rig = kanan[i][j];
if(lef > rig){
ans++;
swap(lef, rig);
}
// cout << lef << " " << rig << " here\n";
swaps.pb(mp(lef, rig));
}
}
sort(swaps.begin(), swaps.end());
memset(tree, 0, sizeof(tree));
for(int i = 0; i < swaps.size(); i++){
int l = swaps[i].first;
int r = swaps[i].second;
long long ans_now = (r - l - 1) - cari(1, 1, 200000, l, r);
ans += ans_now;
upd(1, 1, 200000, l, 1);
upd(1, 1, 200000, r, 1);
}
return ans;
}
// int main(){
// int n; cin >> n;
// vector<int> bawa;
// for(int i = 0; i < n; i++){
// int x; cin >> x;
// bawa.pb(x);
// }
// cout << count_swaps(bawa) << "\n";
// }
