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