#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<double, double> pd;
typedef pair<int, int> pi;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;
const int MAX_N = 2e5 + 100;
int N, M, *S, *X, *Y, *P, *Q;
int Now[MAX_N], To[MAX_N], NowR[MAX_N], ToR[MAX_N];
int sortIx;
bool isSort() {
while(sortIx < N && NowR[sortIx] == ToR[sortIx]) sortIx++;
// printf("sortIx : %d\n", sortIx);
return sortIx == N;
}
bool isCan(int m) {
sortIx = 0;
for(int i=0; i<N; i++) Now[i] = S[i], To[i] = i;
for(int i=0; i<N; i++) NowR[Now[i]] = i, ToR[To[i]] = i;
for(int i=m-1; i>=0; i--) {
int x = X[i], y = Y[i];
swap(ToR[To[x]], ToR[To[y]]);
swap(To[x], To[y]);
}
for(int i=0; i<m; i++) P[i] = 0, Q[i] = 0;
// printf("%d start\n", m);
// printf("N : "); for(int i=0; i<N; i++) printf("%d ", Now[i]); puts("");
// printf("T : "); for(int i=0; i<N; i++) printf("%d ", To[i]); puts("");
if(isSort()) return true;
for(int i=0; i<m; i++) {
int x = X[i], y = Y[i];
swap(ToR[To[x]], ToR[To[y]]);
swap(To[x], To[y]);
swap(NowR[Now[x]], NowR[Now[y]]);
swap(Now[x], Now[y]);
int l = NowR[sortIx], r = ToR[sortIx];
swap(NowR[Now[l]], NowR[Now[r]]);
swap(Now[l], Now[r]);
P[i] = l; Q[i] = r;
// printf("N : "); for(int i=0; i<N; i++) printf("%d ", Now[i]); puts("");
// printf("T : "); for(int i=0; i<N; i++) printf("%d ", To[i]); puts("");
if(isSort()) return true;
}
return false;
}
int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
N = n; M = m; S = s; X = x; Y = y; P = p; Q = q;
int ans = -1;
for(int l=0, r=M; l<=r; ) {
int m = (l+r) >> 1;
if(isCan(m)) ans = m, r = m-1; else l = m+1;
}
isCan(ans);
return ans;
}
