#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200005
#define ll long long
#define FOR(i, a, b) for(ll i = a; i <= b; i++)
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
ll l = 0, h = M;
while(l < h){
int m = (l + h) / 2;
int s[N], slc[N];
FOR(i, 0, N - 1) s[i] = i;
for(int i = m - 1; i >= 0; i--){
swap(s[X[i]], s[Y[i]]);
}
FOR(i, 0, N - 1) slc[s[i]] = i;
queue<int> q;
int s2[N], lc[N];
FOR(i, 0, N - 1) s2[i] = S[i], lc[S[i]] = i;
FOR(i, 0, N - 1) if(slc[i] != lc[i]) q.push(i);
FOR(i, 0, m - 1){
swap(s[X[i]], s[Y[i]]), swap(slc[s[X[i]]], slc[s[Y[i]]]);
swap(s2[X[i]], s2[Y[i]]), swap(lc[s2[X[i]]], lc[s2[Y[i]]]);
while(q.size() && slc[q.front()] == lc[q.front()]){
q.pop();
}
if(q.size()){
int qi = q.front(); q.pop();
P[i] = slc[qi];
Q[i] = lc[qi];
swap(s2[P[i]], s2[Q[i]]), swap(lc[s2[P[i]]], lc[s2[Q[i]]]);
}else{
P[i] = Q[i] = 0;
}
}
FOR(i, 0, N - 1) if(s[i] != s2[i]) {
l = m + 1;
goto spot1;
}
h = m;
spot1:;
}
int m = l;
int s[N], slc[N];
FOR(i, 0, N - 1) s[i] = i;
for(int i = m - 1; i >= 0; i--){
swap(s[X[i]], s[Y[i]]);
}
FOR(i, 0, N - 1) slc[s[i]] = i;
queue<int> q;
int s2[N], lc[N];
FOR(i, 0, N - 1) s2[i] = S[i], lc[S[i]] = i;
FOR(i, 0, N - 1) if(slc[i] != lc[i]) q.push(i);
FOR(i, 0, m - 1){
swap(s[X[i]], s[Y[i]]), swap(slc[s[X[i]]], slc[s[Y[i]]]);
swap(s2[X[i]], s2[Y[i]]), swap(lc[s2[X[i]]], lc[s2[Y[i]]]);
while(q.size() && slc[q.front()] == lc[q.front()]){
q.pop();
}
if(q.size()){
int qi = q.front(); q.pop();
P[i] = slc[qi];
Q[i] = lc[qi];
swap(s2[P[i]], s2[Q[i]]), swap(lc[s2[P[i]]], lc[s2[Q[i]]]);
}else{
P[i] = Q[i] = 0;
}
}
return l;
}
