#include "sorting.h"
#include <bits/stdc++.h>
#define dbg(x) cerr << #x << ' ' <<x << endl;
#define ll long long
using namespace std;
vector<ll> ind;
vector<ll> dest;
vector<ll> recip;
vector<ll> s;
void swp(ll i, ll j)
{
swap(s[i],s[j]);
swap(ind[s[i]],ind[s[j]]);
swap(dest[s[i]],dest[s[j]]);
recip[dest[s[i]]]=s[i];
recip[dest[s[j]]]=s[j];
}
bool is_sorted()
{
for (int i=0;i<s.size();i++)
{
if(s[i]!=i)return false;
}
return true;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
P[0] = 0;
Q[0] = 0;
ind.resize(N);
dest.resize(N);
recip.resize(N);
for (int i=0;i<N;i++)
{
s.push_back(S[i]);
}
for (int i=0;i<N;i++)
{
ind[s[i]]=i;
}
for (int i=0;i<M;i++)
{
P[i]=0;
Q[i]=0;
}
if(is_sorted())
{
return 0;
}
ll l=1;
ll r=M;
ll ans=M;
while(l<=r)
{
ll mid=(l+r)>>1;
for (int i=0;i<N;i++)
{
s[i]=S[i];
ind[s[i]]=i;
}
for (int i=0;i<M;i++)
{
P[i]=0;
Q[i]=0;
}
vector<ll> l3iba(N);
for (int i=0;i<N;i++) l3iba[i]=s[i];
for (int i=0;i<mid;i++)
{
swap(l3iba[X[i]],l3iba[Y[i]]);
}
for (int i=0;i<N;i++)
{
dest[l3iba[i]]=i;
recip[dest[l3iba[i]]]=l3iba[i];
}
ll cur=0;
for (int i=0;i<mid;i++)
{
swap(s[X[i]],s[Y[i]]);
swap(ind[s[X[i]]],ind[s[Y[i]]]);
for (;cur<N;cur++)
{
if(dest[s[cur]]!=s[cur])
{
P[i]=ind[s[cur]];
Q[i]=ind[recip[s[cur]]];
swp(P[i],Q[i]);
break;
}
}
}
if(cur==N)
{
ans=mid;
r=mid-1;
}
else
{
l=mid+1;
}
}
// cout << "here" << endl;
// for (int i=0;i<M;i++)
// {
// cout << X[i] << ' ' << Y[i];
// }
return ans;
}
