#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[]) {
vector<pair<int, int>> res;
function<bool(int)> check = [&](int len) -> bool {
res.resize(len);
vector<int> s(n), pos(n);
for (int i = 0; i < n; i++) {
s[i] = S[i];
pos[S[i]] = i;
}
vector<int> p(n), q(n);
iota(p.begin(), p.end(), 0);
iota(q.begin(), q.end(), 0);
auto do_swap = [&](int i, int j) {
swap(p[i], p[j]);
swap(q[p[i]], q[p[j]]);
};
for (int i = len - 1; i >= 0; i--) {
do_swap(X[i], Y[i]);
}
int l = n - 1;
for (int i = 0; i < len; i++) {
do_swap(X[i], Y[i]);
swap(s[X[i]], s[Y[i]]);
swap(pos[s[X[i]]], pos[s[Y[i]]]);
while (l >= 0 && q[l] == pos[l])
l--;
if (l == -1)
res[i] = {0, 0};
else {
res[i] = {pos[l], q[l]};
}
swap(s[res[i].first], s[res[i].second]);
swap(pos[s[res[i].first]], pos[s[res[i].second]]);
}
while (l >= 0 && q[l] == pos[l]) l--;
return (l == -1);
};
int l = -1, r = m + 1;
while (r - l > 1) {
int mid = (l + r) / 2;
if (check(mid))
r = mid;
else
l = mid;
}
check(r);
for (int i = 0; i < r; i++) {
P[i] = res[i].first;
Q[i] = res[i].second;
}
return r;
}
