#include <bits/stdc++.h>
#include "sorting.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
// #define int long long int
const int N = 2e5 + 10;
const int md = 1e9 + 7;
const int INF = 1e9;
int f(int ch, int n, int s[], int p[], int q[], int x[], int y[]) {
vector<int> e(n), pos(n);
for (int i = 0; i < n; i++) {
e[i] = s[i];
pos[e[i]] = i;
}
for (int i = 0; i < ch; i++) {
swap(pos[e[x[i]]], pos[e[y[i]]]);
swap(e[x[i]], e[y[i]]);
}
int cnt = 0;
for (int i = 0; i < n; i++) {
if (pos[i] == i) continue;
p[cnt] = i, q[cnt] = e[i];
swap(pos[i], pos[e[i]]);
swap(e[i], e[pos[e[i]]]);
cnt++;
}
return cnt;
}
int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
int l = -1, r = m + 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (f(mid, n, s, p, q, x, y) <= mid) r = mid;
else l = mid;
}
// for (int i = 0; i < m; i++)
// p[i] = 0, q[i] = 0;
vector<int> pos(n);
for (int i = 0; i < n; i++)
pos[s[i]] = i;
int co = f(r, n, s, p, q, x, y);
for (int i = 0; i < co; i++) {
swap(pos[s[x[i]]], pos[s[y[i]]]);
swap(s[x[i]], s[y[i]]);
int pp = pos[p[i]], qq = pos[q[i]];
swap(pos[p[i]], pos[q[i]]);
swap(s[pp], s[qq]);
p[i] = pp, q[i] = qq;
}
for (int i = co; i < r; i++)
p[i] = q[i] = 0;
return r;
}
// int32_t main(int32_t argc, char *argv[]) {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// int T = 1;
// // cin >> T;
// while (T--) {
// int n;
// cin >> n;
// int S[n];
// for (int i = 0; i < n; i++)
// cin >> S[i];
// int m;
// cin >> m;
// int x[m], y[m];
// for (int i = 0; i < m; i++)
// cin >> x[i] >> y[i];
// int p[m + 10], q[m + 10];
// cout << findSwapPairs(n, S, m, x, y, p, q) << '\n';
// for (int i = 0; i < 3; i++)
// cout << p[i] << " " << q[i] << '\n';
// }
// return 0;
// }
