#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct dataa{
long long ans = 0;
};
struct Segment_Tree{
vector<dataa>tree;
void init(long long n){
tree.resize(2*n - 1);
}
dataa combine(dataa left,dataa right){
dataa res;
res.ans = left.ans + right.ans;
return res;
}
long long query(long long node,long long left,long long right,long long qleft,long long qright){
if (qright<left|| qleft > right)return 0LL;
if (qleft<=left && qright>=right){
return tree[node].ans;
}
long long mid = (left + right)>>1;
long long z = node + ((mid - left + 1)<<1);
return query(node + 1,left,mid,qleft,qright) + query(z,mid + 1,right,qleft,qright);
}
void update(long long node,long long left,long long right,long long uleft,long long uright,long long v){
if (left > uright || right < uleft) return;
if (uleft <= left && right <=uright){
tree[node].ans+=v;
return;
}
long long mid = (left + right)>>1;
long long z = node + ((mid - left + 1)<<1);
if (uleft<=mid){
update(node + 1,left,mid,uleft,uright,v);
}
if (uright > mid){
update(z,mid + 1,right,uleft,uright,v);
}
tree[node] = combine(tree[node + 1],tree[z]);
}
};
long long count_swaps(std::vector<int> arr) {
int n = (int)arr.size();
map<int,priority_queue<int>>index;
map<int,priority_queue<int>>index2;
Segment_Tree st;
st.init(n);
for (int i = 0;i<n;++i){
if (arr[i] < 0){
index[-arr[i]].push(i);
}
else index2[arr[i]].push(i);
st.update(0,0,n-1,i,i,1);
}
vector<pair<int,int>>brr;
long long ans = 0;
for (auto x:arr){
if (x<0)continue;
while(!index[x].empty()){
brr.push_back({index[x].top(),index2[x].top()});
if (brr.back().first > brr.back().second){
swap(brr.back().first,brr.back().second);
++ans;
}
index[x].pop();
index2[x].pop();
}
}
sort(brr.begin(),brr.end());
for (auto x:brr){
ans+=st.query(0,0,n - 1,x.first,x.second) - 2;
st.update(0,0,n-1,x.first,x.first,-1);
st.update(0,0,n-1,x.second,x.second,-1);
}
return ans;
}
