#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 lo = 0, hi = M;
int temp[N];
vector<int> pos_s(N);
for (int i = 0; i < N; i++) pos_s[S[i]] = i;
for (int i = 0; i < N; i++) temp[i] = S[i];
vector<int> v(N), pos_v(N);
vector<int> temp2 = pos_s;
while (lo < hi) {
int mid = (lo+hi)/2;
for (int i = 0; i < N; i++) v[i] = S[i];
for (int i = 0; i < mid; i++) swap(v[X[i]], v[Y[i]]);
for (int i = 0; i < N; i++) pos_v[v[i]] = i;
int j = 0;
for (int i = 0; i < mid; i++) {
swap(pos_s[S[X[i]]], pos_s[S[Y[i]]]);
swap(S[X[i]], S[Y[i]]);
while (j < N && v[j] == j) j++;
if (j < N) {
int x = pos_s[j];
int y = pos_s[v[j]];
swap(pos_s[S[x]], pos_s[S[y]]);
swap(S[x], S[y]);
int a = pos_v[j], b = pos_v[v[j]];
swap(pos_v[j], pos_v[v[j]]);
swap(v[a], v[b]);
}
}
if (is_sorted(S, S+N)) hi = mid;
else lo = mid+1;
for (int i = 0; i < N; i++) S[i] = temp[i];
pos_s = temp2;
}
for (int i = 0; i < N; i++) v[i] = S[i];
for (int i = 0; i < hi; i++) swap(v[X[i]], v[Y[i]]);
for (int i = 0; i < N; i++) pos_v[v[i]] = i;
int j = 0;
for (int i = 0; i < hi; i++) {
swap(pos_s[S[X[i]]], pos_s[S[Y[i]]]);
swap(S[X[i]], S[Y[i]]);
while (j < N && v[j] == j) j++;
if (j < N) {
int x = pos_s[j];
int y = pos_s[v[j]];
swap(pos_s[S[x]], pos_s[S[y]]);
swap(S[x], S[y]);
P[i] = x, Q[i] = y;
int a = pos_v[j], b = pos_v[v[j]];
swap(pos_v[j], pos_v[v[j]]);
swap(v[a], v[b]);
}
}
return hi;
}
