#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
int a[600005];
int poza[600005], pozv[600005];
int p[600005], q[600005], cv[600005];
int pp[600005], qq[600005];
int findSwapPairs(int n, int v[], int m, int x[], int y[], int P[], int Q[])
{
for(int i = 0; i < n; i++)
cv[i] = v[i];
int st = 0, dr = m;
int r = m;
while(st <= dr)
{
int mij = (st + dr) / 2;
for(int i = 0; i < n; i++)
v[i] = cv[i], a[i] = i, poza[i] = i, pozv[v[i]] = i;
for(int i = 0; i < m; i++)
p[i] = 0, q[i] = 0;
for(int i = mij - 1; i >= 0; i--)
{
swap(poza[a[x[i]]], poza[a[y[i]]]);
swap(a[x[i]], a[y[i]]);
}
int prev = 0, rez = 0;
for(int i = 0; i < mij; i++)
{
swap(poza[a[x[i]]], poza[a[y[i]]]);
swap(a[x[i]], a[y[i]]);
swap(pozv[v[x[i]]], pozv[v[y[i]]]);
swap(v[x[i]], v[y[i]]);
if(prev >= n)
break;
while(prev < n && poza[prev] == pozv[prev])
prev++;
p[i] = pozv[prev];
q[i] = poza[prev];
int le = pozv[prev], ri = poza[prev];
swap(pozv[prev], pozv[v[poza[prev]]]);
swap(v[le], v[ri]);
rez++;
prev++;
}
while(prev < n && poza[prev] == pozv[prev])
prev++;
if(prev >= n)
{
r = rez, dr = mij - 1;
for(int i = 0; i < rez; i++)
pp[i] = p[i], qq[i] = q[i];
}
else
st = mij + 1;
}
for(int i = 0; i < r; i++)
{
P[i] = pp[i], Q[i] = qq[i];
if(P[i] > Q[i])
swap(P[i], Q[i]);
}
return r;
}
