#include "sorting.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
int findSwapPairs(int n, int seq[], int m, int X[], int Y[], int P[], int Q[]) {
P[0] = 0;
Q[0] = 0;
vector<int> per(n), idx(n), mk(n);
int L = -1, R = m, mid;
int d;
while(L + 1 < R){
mid = (L + R) >> 1;
iota(all(per), 0);
fill(all(mk), 0);
d = 0;
for(int i = mid - 1; i >= 0; i--){
d ++;
if(X[i] != Y[i])
swap(per[X[i]], per[Y[i]]);
}
for(int i = 0; i < n; i++) idx[per[i]] = i;
int cnt = 0, nw;
for(int i = 0; i < n; i++){
if(mk[seq[i]]) continue;
cnt ++;
nw = seq[i];
do {
mk[nw] = 1;
nw = seq[idx[nw]];
} while(!mk[nw]);
}
if(n - cnt <= d) R = mid;
else L = mid;
}
cerr << "! " << R << '\n';
iota(all(per), 0);
fill(all(mk), 0);
for(int i = R - 1; i >= 0; i--){
if(X[i] != Y[i])
swap(per[X[i]], per[Y[i]]);
}
for(int i = 0; i < n; i++) idx[per[i]] = i;
set<int> nq;
for(int i = 0; i < n; i++) if(seq[i] != per[i]) nq.insert(i);
for(int i = 0; i < R; i++){
if(X[i] != Y[i]){
nq.erase(X[i]);
nq.erase(Y[i]);
swap(seq[X[i]], seq[Y[i]]);
swap(per[X[i]], per[Y[i]]);
idx[per[X[i]]] = X[i];
idx[per[Y[i]]] = Y[i];
if(seq[X[i]] != per[X[i]])
nq.insert(X[i]);
if(seq[Y[i]] != per[Y[i]])
nq.insert(Y[i]);
}
if(!nq.empty()){
int fr = *nq.begin();
P[i] = fr;
Q[i] = idx[seq[fr]];
assert(P[i] != Q[i]);
nq.erase(P[i]);
nq.erase(Q[i]);
swap(seq[P[i]], seq[Q[i]]);
if(seq[P[i]] != per[P[i]])
nq.insert(P[i]);
if(seq[Q[i]] != per[Q[i]])
nq.insert(Q[i]);
}
}
for(int i = 0; i < n; i++) assert(seq[i] == i);
return R;
}
