#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
bool check(int N, int S[], int M, int T, int X[], int Y[], int P[], int Q[]) {
vector <int> a(N),b(N);
for (int i = 0; i < N; i++) {
a[i] = S[i];
b[i] = S[i];
}
for (int i = 0; i < T; i++) {
swap(b[X[i]],b[Y[i]]);
}
vector <int> pos(N),fpos(N);
for (int i = 0; i < N; i++) {
pos[a[i]] = i;
fpos[b[i]] = i;
}
int cur = 0;
for (int i = 0; i < T; i++) {
swap(a[X[i]],a[Y[i]]);
swap(pos[a[X[i]]],pos[a[Y[i]]]);
while (cur < N) {
if (fpos[cur] != cur) {
P[i] = pos[cur];
Q[i] = pos[b[cur]];
break;
}
cur++;
}
int x = a[P[i]]; int y = a[Q[i]];
swap(b[fpos[x]],b[fpos[y]]);
swap(fpos[x],fpos[y]);
swap(a[P[i]],a[Q[i]]);
swap(pos[a[P[i]]],pos[a[Q[i]]]);
}
for (int i = 0; i < N; i++) {
if (fpos[i] != i) return false;
}
return true;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
P[0] = 0;
Q[0] = 0;
int l = 0; int r = M;
int ans = -1;
while (l <= r) {
int mid = (l+r)/2;
if (check(N,S,M,mid,X,Y,P,Q)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
check(N,S,M,ans,X,Y,P,Q);
return ans;
}
