#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
int solveforM(int n, int st[], int m, int x[], int y[], int p[], int q[]) {
vector<int> a(n); iota(a.begin(), a.end(), 0);
vector<int> s(n); for (int i=0; i<n; i++) s[i] = st[i];
for (int i=m-1; i>=0; i--) swap(a[x[i]], a[y[i]]);
set<int> bad; for (int i=0; i<n; i++) if (a[i] != s[i]) bad.insert(s[i]);
vector<int> posa(n); for (int i=0; i<n; i++) posa[a[i]] = i;
vector<int> poss(n); for (int i=0; i<n; i++) poss[s[i]] = i;
for (int ind=0; ind<m; ind++) {
p[ind] = 0; q[ind] = 0;
swap(a[x[ind]], a[y[ind]]); swap(s[x[ind]], s[y[ind]]);
swap(posa[a[x[ind]]], posa[a[y[ind]]]); swap(poss[s[x[ind]]], poss[s[y[ind]]]);
if (bad.empty()) {
p[ind] = 0; q[ind] = 0; continue;
}
int b = *bad.begin();
int i = poss[b]; int j = posa[b];
p[ind] = i; q[ind] = j;
bad.erase(b);
swap(s[i], s[j]); swap(poss[s[i]], poss[s[j]]);
if (s[i] == a[i]) bad.erase(s[i]);
}
if (bad.empty()) return m;
return 1e9;
}
int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
int l = 0; int r = m;
while (l<r) {
int md = (l+r)/2;
if (solveforM(n,s, md, x,y,p,q) <m) r = md; else l = md+1;
}
solveforM(n,s, l, x,y,p,q);
return l;
}
