#include<bits/stdc++.h>
#include "sorting.h"
using namespace std;
#define pii pair<int,int>
vector<pii> swaps;
vector<pii> evil;
vector<int> arr;
int n;
vector<pii> insertion_sort(vector<int> arr, vector<int> fin, int m){
vector<int> pos(n);
vector<int> posF(n);
for(int i = 0; i < n; i++){
pos[arr[i]] = i;
posF[fin[i]] = i;
}
auto doSwap = [&](int a, int b){
swap(arr[a], arr[b]);
pos[arr[a]] = a;
pos[arr[b]] = b;
};
vector<pii> ops;
for(int i = 0; i < n; i++){
if (ops.size() > m) break;
if(fin[i] == i) continue;
// element that is currently at the position of i
int oth = fin[posF[i]];
int p = fin[i];
doSwap(pos[oth],pos[p]);
ops.push_back({pos[oth],pos[p]});
swap(fin[i], fin[posF[i]]);
posF[fin[i]] = i;
posF[fin[posF[i]]] = posF[i];
doSwap(arr[evil[ops.size()-1].first],arr[evil[ops.size()-1].second]);
}
return ops;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n = N;
int ops = 0;
arr.resize(N);
evil.resize(M);
for(int i = 0; i < M; i++){
evil[i] = {X[i], Y[i]};
}
for(int i = 0; i < n; i++){
arr[i] = S[i];
}
vector<int> cur = arr;
for(int i = 0; i <= M; i++){
auto moves = insertion_sort(arr,cur, i);
if(moves.size() <= i){
insertion_sort(arr,cur, i);
for(int j = 0; j < moves.size(); j++){
P[j] = moves[j].first;
Q[j] = moves[j].second;
}
for(int j = moves.size(); j <= i; j++){
P[j] = Q[j] = 0;
}
return i;
}
if(i == M) break;
swap(cur[evil[i].first], cur[evil[i].second]);
}
return swaps.size();
}
