#include "bits/stdc++.h"
#include "sorting.h"
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
int n,q;
n = N , q = M;
int ar[n+5];
for(int i=1;i<=n;i++) ar[i] = S[i-1]+1;
array<int,2> v[q+5];
for(int i=1;i<=q;i++) v[i][0] = X[i-1]+1 , v[i][1] = Y[i-1]+1;
int l=0,r=q;
vector<array<int,2>> ans;
while(l<r){
int m=(l+r)/2;
int ta[n+5],tb[n+5],a[n+5],b[n+5];
vector<array<int,2>> lol;
for(int i=1;i<=n;i++) ta[i]=tb[i]=i;
for(int i=1;i<=n;i++) a[i]=ar[i];
for(int i=1;i<=n;i++) b[ar[i]]=i;
for(int i=m;i>=1;i--){
int s1 = v[i][0] , s2 = v[i][1];
int v1 = ta[s1] , v2 = ta[s2];
swap(ta[s1],ta[s2]);
tb[v1] = s2;
tb[v2] = s1;
}
int p = n;
for(int i=1;i<=m;i++){
int s1 = v[i][0] , s2 = v[i][1];
int v1 = ta[s1] , v2 = ta[s2];
swap(ta[s1],ta[s2]);
tb[v1] = s2;
tb[v2] = s1;
v1 = a[s1] , v2 = a[s2];
swap(a[s1],a[s2]);
b[v1] = s2;
b[v2] = s1;
while(p>=1 && b[p] == tb[p]) p--;
if(p==0) lol.push_back({1,1});
else{
lol.push_back({b[p],tb[p]});
s1 = b[p] , s2 = tb[p];
v1 = a[s1] , v2 = a[s2];
swap(a[s1],a[s2]);
b[v1] = s2;
b[v2] = s1;
p--;
}
}
while(p>=1 && b[p] == tb[p]) p--;
if(p==0){
r = m;
ans = lol;
}
else l = m + 1;
}
for(int i = 0 ; i < l ; i++){
P[i] = ans[i][0] - 1;
Q[i] = ans[i][1] - 1;
}
return l;
}
/*void _(){
int n,q;
cin >> n >> q;
int ar[n+5];
for(int i=1;i<=n;i++) cin >> ar[i];
array<int,2> v[q+5];
for(int i=1;i<=q;i++) cin >> v[i][0] >> v[i][1];
int l=0,r=q;
vector<array<int,2>> ans;
while(l<r){
int m=(l+r)/2;
int ta[n+5],tb[n+5],a[n+5],b[n+5];
vector<array<int,2>> lol;
for(int i=1;i<=n;i++) ta[i]=tb[i]=i;
for(int i=1;i<=n;i++) a[i]=ar[i];
for(int i=1;i<=n;i++) b[ar[i]]=i;
for(int i=m;i>=1;i--){
int s1 = v[i][0] , s2 = v[i][1];
int v1 = ta[s1] , v2 = ta[s2];
swap(ta[s1],ta[s2]);
tb[v1] = s2;
tb[v2] = s1;
}
int p = n;
for(int i=1;i<=m;i++){
int s1 = v[i][0] , s2 = v[i][1];
int v1 = ta[s1] , v2 = ta[s2];
swap(ta[s1],ta[s2]);
tb[v1] = s2;
tb[v2] = s1;
v1 = a[s1] , v2 = a[s2];
swap(a[s1],a[s2]);
b[v1] = s2;
b[v2] = s1;
while(p>=1 && b[p] == tb[p]) p--;
if(p==0) lol.push_back({1,1});
else{
lol.push_back({b[p],tb[p]});
s1 = b[p] , s2 = tb[p];
v1 = a[s1] , v2 = a[s2];
swap(a[s1],a[s2]);
b[v1] = s2;
b[v2] = s1;
p--;
}
}
while(p>=1 && b[p] == tb[p]) p--;
if(p==0){
r = m;
ans = lol;
}
else l = m + 1;
}
cout << l << '\n';
for(auto x:ans) cout << x[0] << ' ' << x[1] << '\n';
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/
