#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
bool ck(int n,int s[],int m,int x[],int y[]){
if(is_sorted(s,s+n))
return 1;
vector<int> fnal;
vector<int> now;
vector<int> pfnal(n,0);
vector<int> pnow(n,0);
int cnt = 0;
for(int i = 0;i<n;i++){
fnal.push_back(s[i]);
pfnal[s[i]] = i;
now.push_back(s[i]);
pnow[s[i]] = i;
cnt += (s[i] == i);
}
for(int i = 0;i<m;i++){
swap(pfnal[fnal[x[i]]],pfnal[fnal[y[i]]]);
swap(fnal[x[i]],fnal[y[i]]);
}
for(int i = 0;i<m;i++){
if(pnow[now[x[i]]] == now[x[i]])cnt--;
if(pnow[now[y[i]]] == now[y[i]])cnt--;
swap(now[x[i]],now[y[i]]);
swap(pnow[now[x[i]]],pnow[now[y[i]]]);
if(pnow[now[x[i]]] == now[x[i]])cnt++;
if(pnow[now[y[i]]] == now[y[i]])cnt++;
if(i < n){
int ps1 = pnow[i];
int ps2 = pnow[fnal[i]];
if(pnow[now[ps1]] == now[ps1])cnt--;
if(pnow[now[ps2]] == now[ps2])cnt--;
swap(pnow[now[ps1]],pnow[now[ps2]]);
swap(now[ps1],now[ps2]);
if(pnow[now[ps1]] == now[ps1])cnt++;
if(pnow[now[ps2]] == now[ps2])cnt++;
int tmp = pfnal[i];
swap(pfnal[fnal[i]],pfnal[i]);
swap(fnal[i],fnal[tmp]);
}
if(cnt == n)
return 1;
}
return 0;
}
int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
/*int l = 0,r = m;
while(l < r){
int mm = (l + r)/2;
if(ck(n,s,mm,x,y)){
r = mm;
}
else l = mm+1;
}
m = l;*/
for(int i = n;i>=1;i--){
if(ck(n,s,i,x,y)){
m = i;
}
}
if(is_sorted(s,s+n))
return 0;
for(int i = 0;i<m;i++){
p[i] = q[i] = 0;
}
vector<int> fnal;
vector<int> now;
vector<int> pfnal(n,0);
vector<int> pnow(n,0);
int cnt = 0;
for(int i = 0;i<n;i++){
fnal.push_back(s[i]);
pfnal[s[i]] = i;
now.push_back(s[i]);
pnow[s[i]] = i;
cnt += (s[i] == i);
}
for(int i = 0;i<m;i++){
swap(pfnal[fnal[x[i]]],pfnal[fnal[y[i]]]);
swap(fnal[x[i]],fnal[y[i]]);
}
for(int i = 0;i<m;i++){
if(pnow[now[x[i]]] == now[x[i]])cnt--;
if(pnow[now[y[i]]] == now[y[i]])cnt--;
swap(now[x[i]],now[y[i]]);
swap(pnow[now[x[i]]],pnow[now[y[i]]]);
if(pnow[now[x[i]]] == now[x[i]])cnt++;
if(pnow[now[y[i]]] == now[y[i]])cnt++;
if(i < n){
int ps1 = pnow[i];
int ps2 = pnow[fnal[i]];
p[i] = ps1;
q[i] = ps2;
if(pnow[now[ps1]] == now[ps1])cnt--;
if(pnow[now[ps2]] == now[ps2])cnt--;
swap(pnow[now[ps1]],pnow[now[ps2]]);
swap(now[ps1],now[ps2]);
if(pnow[now[ps1]] == now[ps1])cnt++;
if(pnow[now[ps2]] == now[ps2])cnt++;
int tmp = pfnal[i];
swap(pfnal[fnal[i]],pfnal[i]);
swap(fnal[i],fnal[tmp]);
}
if(cnt == n)
return i+1;
}
assert(0);
}
