#include "sorting.h"
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> pii;
void get_order(int c, vector<int> &arr, vector<bool>&vis, vector<int> &to_add) {
if (vis[c])
return;
vis[c] = true;
}
bool try_m(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
vector<int> tmp(S, S + N), where(N), twher(N);
for (int j = 0; j < M; j++)
swap(tmp[X[j]], tmp[Y[j]]);
for (int i = 0; i < N; i++)
where[S[i]] = i, twher[tmp[i]] = i;
vector<pii> to_swap;
for (int i = 0; i < N; i++) {
if (i != tmp[i])
{
to_swap.emplace_back(tmp[i], tmp[twher[i]]);
swap(tmp[i], tmp[twher[i]]);
swap(twher[tmp[i]], twher[tmp[twher[i]]]);
}
}
if (to_swap.size() > M)
return false;
int i;
for (i = 0; i < to_swap.size(); i++) {
// create temp array and do all the swaps
swap(S[X[i]], S[Y[i]]);
swap(where[S[X[i]]], where[S[Y[i]]]);
int get_to_right_place = to_swap[i].first;
int in_my_place = to_swap[i].second;
int id1 = where[get_to_right_place], id2 = where[in_my_place];
swap(S[id1], S[id2]);
swap(where[S[id1]], where[S[id2]]);
P[i] = id1, Q[i] = id2;
}
for (; i < M; i++)
{
P[i] = Q[i] = 0;
swap(S[X[i]], S[Y[i]]);
}
for (int i = 1; i < N; i++)
if (S[i] < S[i - 1])
return false;
return true;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
vector<int> s(S, S + N);
int l = 0, r = M + 1, ans = M;
while (l < r) {
int mid = (l + r) / 2;
if (try_m(N, S, mid, X, Y, P, Q))
ans = mid, r = mid;
else
l = mid + 1;
for (int i = 0; i < N; i++)
S[i] = s[i];
}
try_m(N, S, ans, X, Y, P, Q);
return ans;
}
