#include "shoes.h"
//#include "grader.cpp"
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define endl "\n"
#define all(v) v.begin(),v.end()
#define gen(arr,n,nxt) generate(arr,arr+n,nxt)
#define Blobo2 ios_base::sync_with_stdio(false);cin.tie(0);
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<long long,long long>, null_type,less<pair<long long,long long>>, rb_tree_tag,tree_order_statistics_node_update>
//s.order_of_key(x)
//s.find_by_order(idx)
long long count_swaps(vector<int32_t> v) {
int n = v.size();
long long arr[n];
for(int i=0;i<n;i++)arr[i] = abs(v[i]);
ordered_set st;
long long cnt=0;
for(int i=n-1;i>=0;i--){
st.insert({arr[i],i});
int idx = st.order_of_key(make_pair(arr[i],i));
cnt += idx;
}
stack<int>s[(n/2)+1];
bool vis[n];
memset(vis,0,sizeof vis);
for(int i=n-1;i>=0;i--){
if(v[i] > 0){
s[v[i]].push(i);
}
else{
if(!s[-v[i]].empty()){
vis[s[-v[i]].top()] = 1;
s[-v[i]].pop();
vis[i] = 1;
}
}
}
int c = 0;
for(int i=0;i<n;i++)c += vis[i] == 0;
c/=2;
cnt += c;
return cnt;
}
