#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
//static FILE *_inputFile, *_outputFile;
int n;
vector<pair<int,int> > v;
int p[200001],pos[200001];
void swaps()
{
for(int i=0; i<n; i++)
pos[p[i]]=i;
for(int i=0; i<n; i++)
{
if(p[i]!=i)
{
v.push_back({i,p[i]});
pos[p[i]]=pos[i];
swap(p[i],p[pos[i]]);
}
}
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[],int P[],int Q[])
{
n=N;
int ans=0;
int l=0,r=M;
while(l<=r)
{
int m=(l+r)/2;
for(int i=0; i<n; i++)
p[i]=S[i];
for(int i=0; i<m; i++)
swap(p[X[i]],p[Y[i]]);
v.clear();
swaps();
if(v.size()<=m)
{
r=m-1;
ans=m;
}
else l=m+1;
}
for(int i=0; i<n; i++)
p[i]=S[i];
for(int i=0; i<ans; i++)
swap(p[X[i]],p[Y[i]]);
v.clear();
swaps();
//for(int i=0;i<ans;i++)
// fprintf(_outputFile, "%d %d ", v[i].first, v[i].second);
for(int i=0;i<n;i++)
p[i]=S[i];
for(int i=0; i<n; i++)
pos[p[i]]=i;
for(int i=0; i<ans; i++)
{
pos[p[Y[i]]]=X[i];
pos[p[X[i]]]=Y[i];
swap(p[X[i]],p[Y[i]]);
P[i]=pos[v[i].first];
Q[i]=pos[v[i].second];
if(P[i]>Q[i])swap(P[i],Q[i]);
pos[p[P[i]]]=Q[i];
pos[p[Q[i]]]=P[i];
swap(p[P[i]],p[Q[i]]);
}
return ans;
}
/*
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>p[i];
}
*/
