#include<bits/stdc++.h>
#include "sorting.h"
using namespace std;
#define pii pair<int,int>
vector<pii> swaps;
vector<int> arr;
int getMedian(vector<int> arr){
sort(arr.begin(),arr.end());
return arr[(arr.size()-1)/2];
}
void quicksort(int l, int r){
if(l == r) return;
vector<int> cur;
for(int i = l; i <= r; i++){
cur.push_back(arr[i]);
}
int mid = l+((cur.size()-1)/2);
int med = getMedian(cur);
int rpt = r;
for(int i = l; i <= mid; i++){
while(rpt > cur.size()/2 && arr[rpt] > med){
rpt--;
}
if(arr[i] > med){
swaps.push_back({i,rpt});
swap(arr[i], arr[rpt]);
rpt--;
}
}
quicksort(l, mid);
quicksort(mid+1, r);
}
int findSwapPairs(int n, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int ops = 0;
arr.resize(n);
for(int i = 0; i < n; i++){
arr[i] = S[i];
}
quicksort(0,n-1);
for(int i = 0; i < swaps.size(); i++){
P[i] = swaps[i].first;
Q[i] = swaps[i].second;
}
return swaps.size();
}
