#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int N, M;
int pos[200005];
int S[200005], A[200005];
int X[600005], Y[600005];
int P[600005], Q[600005];
int pp;
void balance(int now) {
while(pp <= now) swap(S[X[pp]], S[Y[pp]]), pp++;
while(pp > now + 1) swap(S[X[pp - 1]], S[Y[pp - 1]]), pp--;
}
bool trysort(int limit) {
int cnt = 0;
// cout << limit << "\n";
for(int i = 0; i < N; i++) {
A[i] = S[i];
// cout << A[i] << " ";
pos[A[i]] = i;
}
// cout << "\n";
for(int i = 0; i < N; i++) {
if(A[i] != i) {
P[cnt] = i, Q[cnt] = pos[i];
cnt++;
int b = A[i];
swap(A[i], A[pos[i]]);
pos[b] = pos[i];
pos[i] = i;
// for(int j = 0; j < N; j++) {
// cout << A[j] << " ";
// }
// cout << "\n";
}
}
for(int i = cnt; i < limit; i++) {
P[i] = 0, Q[i] = 0;
}
// cout << cnt << "\n\n";
return cnt <= limit;
}
int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
N = n, M = m;
for(int i = 0; i < N; i++) S[i] = s[i];
for(int i = 1; i <= M; i++) X[i] = x[i - 1], Y[i] = y[i - 1];
int l = 0, r = M, res = 0;
while(l <= r) {
int mid = (l + r) >> 1;
balance(mid);
if(trysort(mid)) {
res = mid;
r = mid - 1;
}else l = mid + 1;
}
trysort(res);
for(int i = 0; i < res; i++) {
p[i] = P[i], q[i] = Q[i];
}
// system("pause");
return res;
}
