#include "sorting.h"
#include <cstdio>
#include <algorithm>
using namespace std;
int tree[200006], tree_cnt[524288];
int query(int i, int b, int e) {
if (b == e) return b;
int m = (b + e) / 2;
if (tree_cnt[i * 2 + 1] < m - b + 1) return query(i * 2 + 1, b, m);
else return query(i * 2 + 2, m + 1, e);
}
int update(int i, int b, int e, int p, int v) {
if (p < b || e < p) return tree_cnt[i];
if (b == e) return tree_cnt[i] = v;
int m = (b + e) / 2;
return tree_cnt[i] = update(i * 2 + 1, b, m, p, v) + update(i * 2 + 2, m + 1, e, p, v);
}
int curr[200006], curr_rev[200006];
bool visited[200006];
int getCycle(int n) {
int cnt = 0;
for (int i = 0; i < n; i++) visited[i] = false;
for (int i = 0; i < n; i++) if (!visited[i]) {
int j = curr[i];
visited[i] = true;
while (j != i) {
visited[j] = true;
j = curr[j];
}
cnt++;
}
return cnt;
}
int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
auto f = [&](int z) {
for (int i = 0; i < n; i++) curr[i] = s[i];
for (int t = 0; t < z; t++) swap(curr[x[t]], curr[y[t]]);
return n - getCycle(n);
};
int l = 0, r = m;
while (l < r) {
int mid = (l + r) / 2;
if (f(mid) <= mid) r = mid;
else l = mid + 1;
}
for (int i = 0; i < n; i++) tree[i] = s[i], curr[i] = curr_rev[i] = i;
for (int i = 0; i < l; i++) swap(tree[x[i]], tree[y[i]]);
for (int i = 0; i < n; i++) tree_cnt[262143 + i] = tree[i] == i;
for (int i = 262142; i >= 0; i--) tree_cnt[i] = tree_cnt[i * 2 + 1] + tree_cnt[i * 2 + 2];
for (int t = l - 1; t >= 0; t--) {
int it = query(0, 0, 262143);
if (it == n) break;
p[t] = curr_rev[tree[it]];
q[t] = it;
update(0, 0, 262143, it, 1);
swap(curr[p[t]], curr[q[t]]);
swap(curr_rev[curr[p[t]]], curr_rev[curr[q[t]]]);
if (curr[p[t]] == tree[p[t]]) update(0, 0, 262143, p[t], 1);
swap(curr[x[t]], curr[y[t]]);
swap(curr_rev[curr[x[t]]], curr_rev[curr[y[t]]]);
swap(tree[x[t]], tree[y[t]]);
int tmp = tree_cnt[262143 + x[t]];
update(0, 0, 262143, x[t], tree_cnt[262143 + y[t]]);
update(0, 0, 262143, y[t], tmp);
}
return l;
}
