#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
int ans = 0;
for(int round = 0; round < m; ++round) {
if(is_sorted(s, s + n)) {
return ans;
}
swap(s[x[round]], s[y[round]]);
// we assume that after m rounds it will def be swapped
vector<int> ord(n); iota(ord.begin(), ord.end(), 0);
// ord[i] = i; at last since it's sorted
for(int j = m - 1; j > round; --j) {
swap(ord[x[j]], ord[y[j]]);
}
vector<int> inv_s(n);
for(int i = 0; i < n; ++i) {
inv_s[s[i]] = i;
}
for(int i = 0; i < n; ++i) {
if(s[i] != ord[i]) {
int k = inv_s[ord[i]];
swap(s[k], s[i]);
p[ans] = k;
q[ans] = i;
goto end;
}
}
// for(int i = 0; i < n; ++i) {
// if(s[i] != ord[i]) { // ith element isn't in its place look for who is in its place
// for(int k = i + 1; k < n; ++k) {
// if(s[k] == ord[i]) {
// swap(s[k], s[i]);
// p[ans] = k;
// q[ans] = i;
// goto end;
// }
// }
// }
// }
p[ans] = q[ans] = n - 1; // already sorted no change needed
end:;
++ans;
}
return ans;
}
