#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]]);
vector<int> bad(n+1,0); for (int i=0; i<n; i++) if (a[i] != s[i]) bad[s[i]] = 1;
bad[n] = 1;
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;
int lb = 0;
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]]]);
int b = lb; while (!bad[b]) b = ++lb; if (lb == n) {p[ind] =0; q[ind] = 0; continue;};
int i = poss[b]; int j = posa[b];
p[ind] = i; q[ind] = j;
bad[b] = 0;
swap(s[i], s[j]); swap(poss[s[i]], poss[s[j]]);
if (s[i] == a[i]) bad[s[i]] = 0;
}
while (!bad[lb]) lb++;
if (lb == n) 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;
}
