#include "shoes.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
typedef long long ll;
using namespace std;
vector<long long> kiri[200005], kanan[200005];
vector<pair<long long,long long> > swaps;
long long tree[4 * 200005];
void upd(long long idx, long long l, long long r, long long titik, long long 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];
}
long long cari(long long idx, long long l, long long r, long long kiri, long long kanan){
if(kiri > r || kanan < l){
return 0;
}
if(l >= kiri && r <= kanan){
return tree[idx];
}
long long satu = cari(2 * idx, l, (l + r)/2, kiri, kanan);
long long dua = cari(2 * idx + 1, (l + r)/2 + 1, r, kiri, kanan);
return satu + dua;
}
long long count_swaps(vector<int> s) {
long long n = s.size() / 2;
for(long long i = 0; i < s.size(); i++){
if(s[i] < 0){
kiri[-s[i]].pb(i + 1);
}else{
kanan[s[i]].pb(i + 1);
}
}
long long ans = 0;
for(long long i = 1; i < s.size() + 5; i++){
for(long long j = 0; j < kiri[i].size(); j++){
long long lef = kiri[i][j];
long long 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(long long i = 0; i < swaps.size(); i++){
long long l = swaps[i].first;
long long 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";
// }
