#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 && fpos[cur] != cur) { P[i] = pos[cur]; Q[i] = pos[b[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; }