#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
bool check(int n,int S[],int perm[],int permsuf[],int m,int X[],int Y[],int P[],int Q[],int posp[],int posps[]){
int i;
for(i=0;i<n;++i){
perm[i]=S[i];
permsuf[i]=i;
posp[perm[i]]=i;
posps[i]=i;
}
for(i=0;i<m;++i){
int x=X[i];
int y=Y[i];
swap(perm[x],perm[y]);
swap(posp[perm[x]],posp[perm[y]]);
swap(permsuf[x],permsuf[y]);
swap(posps[permsuf[x]],posps[permsuf[y]]);
}
int id=0;
for(i=0;i<m;++i){
int x=X[i];
int y=Y[i];
int px=posps[x];
int py=posps[y];
swap(permsuf[px],permsuf[py]);
swap(posps[x],posps[y]);
while(id<n && id==perm[id])
++id;
if(id<n){
int p1=id;
int p2=perm[id];
int val1=permsuf[p1];
int val2=permsuf[p2];
P[i]=val1;
Q[i]=val2;
swap(perm[p1],perm[p2]);
swap(posp[perm[p1]],posp[perm[p2]]);
}
else{
P[i]=0;
Q[i]=0;
}
}
for(i=0;i<n;++i)
if(perm[i]!=i)
return 0;
return 1;
}
int const MAX=2e5+5;
int perm[MAX],posp[MAX],permsuf[MAX],posps[MAX];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
/// (]
int st=-1,dr=M;
while(dr-st>1){
int mij=(st+dr)/2;
if(check(N,S,perm,permsuf,mij,X,Y,P,Q,posp,posps))
dr=mij;
else
st=mij;
}
check(N,S,perm,permsuf,dr,X,Y,P,Q,posp,posps);
return dr;
}
