#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;
struct segment_tree{
vector<int>a;
int sz = 1;
segment_tree(int n){
while(sz < n) sz*=2;
a.assign(sz*2,0);
}
void update(int i,int v,int x=0,int lx=0,int rx=-1){
if(rx == -1) rx = sz;
if(rx-lx == 1){
a[x] = v;
return;
}
int m = (lx+rx)/2;
if(i < m){
update(i,v,x*2+1,lx,m);
}else{
update(i,v,x*2+2,m,rx);
}
a[x] = a[x*2+1] + a[x*2+2];
}
int get(int l,int r,int x=0,int lx=0,int rx=-1){
if(rx == -1) rx = sz;
if(rx <= l || lx >= r) return 0;
if(l <= lx && r >= rx) return a[x];
int m = (lx+rx)/2;
int s1 = get(l,r,x*2+1,lx,m);
int s2 = get(l,r,x*2+2,m,rx);
return s1+s2;
}
};
long long count_swaps(vector<int> a){
int n = a.size();
int N = n/2;
vector<vector<int>>idx(n+1);
vector<int>ptr(n+1,0);
long long ans = 0;
vector<bool>vis(n,0);
for(int i = 0; i < n; i++){
idx[a[i]+N].push_back(i);
}
segment_tree st(n);
for(int i = 0; i < n; i++){
if(vis[i]) continue;
int search = -1;
if(a[i] > 0){
int x = a[i]*2;
int y = a[i]+N;
search = y-x;
ans++;
}else{
int x = (-a[i])+N;
search = x;
}
int j = idx[search][ptr[search]];
ptr[search]++;
ptr[a[i]+N]++;
// cout << j << ' ';
vis[j] = 1;
st.update(j,1);
j -= st.get(i,j);
// cout << j << ' ' << i << '\n';
cout.flush();
ans += j-(i+1);
// cout << ans << '\n';cout.flush();
}
return ans;
}
// int main(){
// vector<int> a = {2, 1, -1, -2};
// cout << count_swaps(a) << '\n';
// }
