#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
bool solve(int n, vector<int> a, vector<int> ainv, int m, int X[], int Y[], int P[], int Q[]){
vector<int> p(n), pinv(n);
for(int i = 0; i < n; i++) p[i] = pinv[i] = i;
for(int i = 0; i < m; i++){
swap(p[pinv[X[i]]], p[pinv[Y[i]]]);
swap(pinv[X[i]], pinv[Y[i]]);
}
int cur = 0;
for(int i = 0; i < m; i++){
swap(p[X[i]], p[Y[i]]);
swap(pinv[p[X[i]]], pinv[p[Y[i]]]);
swap(a[X[i]], a[Y[i]]);
swap(ainv[a[X[i]]], ainv[a[Y[i]]]);
P[i] = Q[i] = 0;
while(cur < n && cur == p[ainv[cur]]) cur++;
if(cur < n){
P[i] = ainv[cur];
Q[i] = pinv[cur];
swap(a[P[i]], a[Q[i]]);
swap(ainv[a[P[i]]], ainv[a[Q[i]]]);
}
}
for(int i = 0; i < n; i++) if(a[i] != i) return false;
return true;
}
int findSwapPairs(int n, int S[], int M, int X[], int Y[], int P[], int Q[]) {
vector<int> a(n), ainv(n);
for(int i = 0; i < n; i++) a[i] = S[i], ainv[S[i]] = i;
int lo = 0, hi = M-1;
for(int mid=(lo+hi)/2; lo<hi; mid=(lo+hi)/2){
if(solve(n, a, ainv, mid, X, Y, P, Q)) hi = mid;
else lo = mid+1;
}
solve(n, a, ainv, lo, X, Y, P, Q);
return lo;
}
