#include <bits/stdc++.h>
using namespace std;
const int MAXN=200000;
int E[MAXN], I[MAXN], S[MAXN], F[MAXN];
bool can(int e, int N, int S_[], int X[], int Y[], vector<pair<int,int>> &ans){
ans.clear();
ans.resize(e, {0,0});
for(int i=0;i<N;i++){
S[i]=S_[i];
E[S[i]]=i;
F[i]=i;
}
for(int i=0;i<e;i++){
swap(F[X[i]], F[Y[i]]);
}
for(int i=0;i<N;i++){
I[F[i]]=i;
}
int u=0,j=0;
for(int i=0;i<e;i++){
int a=X[i], b=Y[i];
swap(S[a], S[b]);
swap(I[a], I[b]);
F[I[a]]=E[S[a]]=a;
F[I[b]]=E[S[b]]=b;
while(u<N&&E[u]==F[u])u++;
if(u==N)break;
int aa=E[u], bb=F[u];
ans[j]={aa,bb};
swap(S[aa], S[bb]);
E[S[aa]]=aa;
E[S[bb]]=bb;
j++;
}
/* for(int i=0;i<N;i++){
cout<<S[i]<<" ";
}
cout<<endl; */
while(u<N&&E[u]==F[u])u++;
return u==N;
}
int findSwapPairs(int N, int S_[], int M, int X[], int Y[], int P[], int Q[]){
if(is_sorted(S_, S_+N)){
return 0;
}
int l=0,r=M;
vector<pair<int,int>> a, b;
while(r-l>1){
int m=(r+l)/2;
if(can(m,N,S_,X,Y,b)){
r=m;
a=b;
}else l=m;
}
for(int i=0;i<r;i++){
P[i]=a[i].first;
Q[i]=a[i].second;
}
return r;
}
