#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
int n,m;
pair<int,int> his[600005],sol[600005];
int init[200005],ord[200005],unde[200005],final[200005],ufin[200005];
bool is_sorted()
{
for(int i=1;i<n;i++)
if(ord[i]<ord[i-1])
return 0;
return 1;
}
bool verif(int ult)
{
for(int i=0;i<n;i++)
ord[i] = final[i] = init[i];
for(int i=0;i<=ult;i++)
swap(final[his[i].first], final[his[i].second]);
for(int i=0;i<n;i++)
unde[ord[i]] = i;
for(int i=0;i<n;i++)
ufin[final[i]] = i;
vector<int> gresite;
for(int i=0;i<n;i++)
if(final[i]!=i)
gresite.push_back(i);
int poz=0;
for(int pas=0;pas<=ult;pas++)
{
swap(unde[ord[his[pas].first]], unde[ord[his[pas].second]]);
swap(ord[his[pas].first],ord[his[pas].second]);
pair<int,int> aux = {-1,-1};
while(poz<gresite.size() && final[gresite[poz]]==gresite[poz])
poz++;
if(poz < gresite.size())
aux = {final[gresite[poz]], gresite[poz]};
if(aux.first!=-1)
{
sol[pas].first = unde[aux.first];
sol[pas].second = unde[aux.second];
swap(ufin[aux.first], ufin[aux.second]);
swap(final[ufin[aux.first]], final[ufin[aux.second]]);
swap(unde[ord[sol[pas].first]], unde[ord[sol[pas].second]]);
swap(ord[sol[pas].first], ord[sol[pas].second]);
}
else
sol[pas] = {0,0};
}
for(int i=0;i<n;i++)
ord[i] = init[i];
for(int pas=0;pas<=ult;pas++)
{
swap(ord[his[pas].first], ord[his[pas].second]);
swap(ord[sol[pas].first], ord[sol[pas].second]);
}
return is_sorted();
}
int findSwapPairs(int N, int copS[], int M, int X[], int Y[], int P[], int Q[])
{
n = N;
m = M;
for(int i=0;i<N;i++)
{
init[i] = copS[i];
ord[i] = init[i];
}
for(int i=0;i<M;i++)
{
his[i] = {X[i], Y[i]};
}
if(is_sorted())
return 0;
int st=0,dr=m-2,ans=m-1;
while(st<=dr)
{
int mij=(st+dr)/2;
if(verif(mij))
{
ans = mij;
dr = mij-1;
}
else
st = mij+1;
}
assert(verif(ans));
for(int i=0;i<=ans;i++)
{
P[i] = sol[i].first;
Q[i] = sol[i].second;
}
return ans+1;
}
