#include<bits/stdc++.h>
#include "sorting.h"
using namespace std;
const int MAX_SWAP=600*1000+5;
int nbVal,nbSwap,posModif,nouvVal,deb,fin,mid;
int autreSwap[MAX_SWAP][2];
int val[MAX_SWAP];
int posDansObj[MAX_SWAP];
int obj[MAX_SWAP];
vector<pair<int,int>> nouv;
vector<pair<int,int>> rep;
deque<int> listePb;
void maj(int pos) {
if (val[pos]!=obj[pos]) {
listePb.push_back(pos);
}
while (!listePb.empty() and val[listePb.front()]==obj[listePb.front()]) {
listePb.pop_front();
}
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
nbVal=N;
nbSwap=M;
for (int i=0;i<nbVal;i++) {
val[i]=S[i];
}
for (int i=0;i<nbSwap;i++) {
autreSwap[i][0]=X[i];
autreSwap[i][1]=Y[i];
}
fin=nbSwap;
rep.resize(nbSwap);
while (deb!=fin) {
mid=(deb+fin)/2;
nouv.clear();
listePb.clear();
for (int i=0;i<nbVal;i++) {
obj[i]=i;
posDansObj[i]=i;
}
for (int i=0;i<nbVal;i++) {
val[i]=S[i];
}
for (int i=mid-1;i>=0;i--) {
posDansObj[obj[autreSwap[i][0]]]=autreSwap[i][1];
posDansObj[obj[autreSwap[i][1]]]=autreSwap[i][0];
swap(obj[autreSwap[i][0]],obj[autreSwap[i][1]]);
}
for (int i=0;i<nbVal;i++) {
maj(i);
}
for (int i=0;i<mid;i++) {
posDansObj[obj[autreSwap[i][0]]]=autreSwap[i][1];
posDansObj[obj[autreSwap[i][1]]]=autreSwap[i][0];
swap(obj[autreSwap[i][0]],obj[autreSwap[i][1]]);
swap(val[autreSwap[i][0]],val[autreSwap[i][1]]);
maj(autreSwap[i][0]);
maj(autreSwap[i][1]);
if (listePb.empty()) {
posModif=0;
}
else {
posModif=listePb.front();
}
nouvVal=posDansObj[val[posModif]];
nouv.push_back({posModif,nouvVal});
swap(val[posModif],val[nouvVal]);
maj(posModif);
maj(nouvVal);
}
if (!listePb.empty()) {
deb=mid+1;
}
else {
fin=mid;
if (nouv.size()<rep.size()) {
rep=nouv;
}
}
}
for (int i=0;i<deb;i++) {
P[i]=rep[i].first;
Q[i]=rep[i].second;
}
return deb;
}
