#include "sorting.h"
#include <algorithm>
#include <cstring>
const int MAXN = 2e5;
int N, M, *S, *X, *Y, *P, *Q;
int fp[MAXN + 10];
int carry[MAXN + 10];
int wfp[MAXN + 10];
int platei[MAXN + 10];
int plateid[MAXN + 10];
void swap_plate(int x, int y) {
int xp = plateid[x], yp = plateid[y];
std::swap(platei[xp], platei[yp]);
std::swap(plateid[x], plateid[y]);
}
bool oka(int R) {
std::fill(P, P + M, 0); std::fill(Q, Q + M, 0);
for(int i = 0; i < N; i++) {
platei[i] = plateid[i] = fp[i] = i;
carry[i] = S[i];
}
for(int i = 0; i < R; i++) {
int x = X[i], y = Y[i];
swap_plate(x, y);
}
for(int i = 0; i < N; i++) {
fp[i] = platei[i];
wfp[fp[i]] = i;
}
for(int i = 0; i < N; i++) {
platei[i] = i;
}
int x = 0;
for(int i = 0; i < R; i++) {
swap_plate(X[i], Y[i]);
while(x < N && fp[x] == carry[x]) {
x++;
}
if(x == N) break;
int y = wfp[carry[x]];
P[i] = platei[x]; Q[i] = platei[y];
std::swap(carry[x], carry[y]);
}
while(x < N && fp[x] == carry[x]) {
x++;
}
return x == N;
}
int findSwapPairs(int N_, int S_[], int M_, int X_[], int Y_[], int P_[], int Q_[]) {
N = N_; M = M_; S = S_; X = X_; Y = Y_; P = P_; Q = Q_;
int lo = 0, hi = M;
while(lo < hi) {
int m = (lo + hi) / 2;
if(oka(m)) hi = m;
else lo = m + 1;
}
oka(lo);
return lo;
}
