#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);
map<int,int> pos;
for(int i = 0; i < n; i++){
arr[i] = S[i];
pos[arr[i]] = i;
}
if(n == 1){
return 0;
}
if(n == 2){
if(arr[0] == 1 && arr[1] == 0){
return 1;
}else{
return 0;
}
}
swaps.push_back({0, pos[1]});
swap(arr[0], arr[pos[1]]);
swap(arr[X[0]], arr[Y[0]]);
for(int i = 0; i < n; i++){
pos[arr[i]] = i;
}
swaps.push_back({0, pos[0]});
if(arr[0] != 0){
swap(arr[0], arr[pos[0]]);
swap(arr[X[1]], arr[Y[1]]);
}else{
swap(arr[1], arr[pos[0]]);
swap(arr[X[1]], arr[Y[1]]);
}
quicksort(2,n-1);
for(int i = 0; i < swaps.size(); i++){
if(i > 1){
swap(arr[0], arr[1]);
}
}
if(arr[0] == 1 && arr[1] == 0){
if(X[0] == 0 && Y[0] == 1){
swaps.push_back({0,0});
}else{
swaps.push_back({0,1});
}
swap(arr[0], arr[1]);
}
for(int i = 0; i < swaps.size(); i++){
P[i] = swaps[i].first;
Q[i] = swaps[i].second;
}
return swaps.size();
}
