#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
bool check(int n, int xs[], int k, int ss1[], int ss2[], int ans1[] = nullptr, int ans2[] = nullptr) {
vector<int> ideal(n), idealrev(n), ys(n), ysrev(n);
for (int i = 0; i < n; ++i)
ideal[i] = idealrev[i] = ysrev[ys[i] = xs[i]] = i;
for (int i = k-1; i >= 0; --i) {
swap(ideal[ss1[i]], ideal[ss2[i]]);
swap(idealrev[ideal[ss1[i]]], idealrev[ideal[ss2[i]]]);
}
int lst = 0;
for (int i = 0; i < k; ++i) {
swap(ideal[ss1[i]], ideal[ss2[i]]);
swap(idealrev[ideal[ss1[i]]], idealrev[ideal[ss2[i]]]);
swap(ys[ss1[i]], ys[ss2[i]]);
swap(ysrev[ys[ss1[i]]], ysrev[ys[ss2[i]]]);
cerr << "-> " << lst << " " << idealrev[lst] << " " << ysrev[lst] << "\n";
while (lst < n && idealrev[lst] == ysrev[lst]) ++lst;
if (lst < n) {
int a = ysrev[lst], b = idealrev[lst];
swap(ys[a], ys[b]);
swap(ysrev[ys[a]], ysrev[ys[b]]);
if (ans1 != nullptr) { ans1[i] = a; ans2[i] = b; }
}
else if (ans1 != nullptr) { ans1[i] = 0; ans2[i] = 0; }
}
for (int i = 0; i < n; ++i)
if (ys[i] != i) return false;
// cerr << k << "TRUE\n";
return true;
}
int findSwapPairs(int n, int xs[], int m, int ss1[], int ss2[], int ans1[], int ans2[]) {
int l = 1, r = m;
while (l < r) {
int mid = (l + r)/2;
if (check(n, xs, mid, ss1, ss2)) r = mid;
else l = mid + 1;
}
check(n, xs, r, ss1, ss2, ans1, ans2);
return r;
}
