#include <bits/stdc++.h>
using namespace std;
vector<int> tree;
int len=0;
void update(int v,int currStart,int currEnd,int lookStart,int lookEnd){
if (currStart>=lookStart && currEnd<=lookEnd){
tree[v]++;
return;
}
if (currStart>lookEnd || currEnd<lookStart) return;
int mid=(currStart+currEnd)/2;
update(2*v,currStart,mid,lookStart,lookEnd);
update(2*v,mid+1,currEnd,lookStart,lookEnd);
}
int get(int pos){
pos+=len;
int ans=tree[pos];
while (pos>1){
pos/=2;
ans+=tree[pos];
}
return ans;
}
int64_t count_swaps(vector<int> S){
tree.clear();
int n=S.size();
for (int i=1;i<=21;i++){
int p=(1<<i);
if (p>=n){
len=p;
break;
}
}
tree.resize(2*len);
for (int i=0;i<n;i++) tree[i+len]=i;
int swaps=0;
vector<pair<priority_queue<int,vector<int>,greater<>>,priority_queue<int,vector<int>,greater<>>>> pqs(n+1);
vector<bool> skip(n+1);
for (int i=0;i<n;i++){
if (S[i]<0){
//.first
pqs[S[i]*-1].first.push(i);
} else {
//.second
pqs[S[i]].second.push(i);
}
}
for (int i=0;i<n;i++){
if (skip[i]) continue;
int now=get(i);
int next;
if (S[i]<0){
next=pqs[S[i]*-1].second.top();
pqs[S[i]*-1].second.pop();
pqs[S[i]*-1].first.pop();
} else {
next=pqs[S[i]].first.top();
pqs[S[i]].first.pop();
pqs[S[i]].second.pop();
}
next=get(next);
cout<<now<<" "<<next<<"\n";
skip[now]=true;
skip[next]=true;
swaps+=next-now-1;
if (S[i]>0) swaps++;
update(1,0,len-1,0,next-1);
}
return swaps;
}
