#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
int n;
vector<int> ss, x, y;
vector<pii> ans;
bool check(int m){
ans.clear();
ans.resize(m, mp(0, 0));
vector<int> f(n), id(n), s=ss, b(n), bid(n);
for (int i=0; i<n; ++i)f[i]=i, id[s[i]]=i;
for (int i=0; i<m; ++i)swap(f[x[i]], f[y[i]]);
for (int i=0; i<n; ++i)b[f[i]]=i, bid[b[f[i]]]=i;
for (int i=0; i<n; ++i)assert(bid[i]==f[i]);
int p=0;
for (int i=0; i<m; ++i){
swap(s[x[i]], s[y[i]]);
swap(b[x[i]], b[y[i]]);
id[s[x[i]]]=x[i];
id[s[y[i]]]=y[i];
bid[b[x[i]]]=x[i];
bid[b[y[i]]]=y[i];
while (p<n&&id[p]==bid[p])++p;
if (p==n)break;
pii temp = mp(id[p], bid[p]);
swap(s[temp.fi], s[temp.se]);
id[s[temp.fi]]=temp.fi;
id[s[temp.se]]=temp.se;
ans[i]=temp;
}
while (p<n&&id[p]==bid[p])++p;
return p==n;
}
int findSwapPairs(int N, int S[], int m, int X[], int Y[], int p[], int q[]){
n=N;
ss.clear();
x.clear();
y.clear();
ss.resize(n);
x.resize(m);
y.resize(m);
for (int i=0; i<n; ++i)ss[i]=S[i];
for (int i=0; i<m; ++i)x[i]=X[i], y[i]=Y[i];
int low=-1, high=m+1;
while (low+1<high){
int mid=(low+high)/2;
if (check(mid))high=mid;
else low=mid;
}
check(high);
for (int i=0; i<high; ++i)p[i]=ans[i].fi, q[i]=ans[i].se;
return high;
}
