#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int tab[15005][505];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
for (int i = 0; i < N; ++i)
tab[M-1][i]=i,tab[M][i]=i;
map<int,int> pos;
for (int i = 0; i < N; ++i)
pos[S[i]]=i;
for (int i = M-1; i >=0 ; i--)
{
swap(tab[i][X[i]],tab[i][Y[i]]);
if(i)
for (int j = 0; j < N; ++j)
tab[i-1][j]=tab[i][j];
}
for (int i = 0; i < M; ++i)
{
P[i]=Q[i]=0;
swap(pos[S[X[i]]],pos[S[Y[i]]]);
swap(S[X[i]],S[Y[i]]);
if(i==(M-1)){
for (int j = 0; j < N; ++j)
if(tab[i+1][j]!=S[j]){
P[i]=j,Q[i]=pos[tab[i+1][j]];
swap(pos[S[P[i]]],pos[S[Q[i]]]);
swap(S[P[i]],S[Q[i]]);
break;
}
continue;
}
if(tab[i+1][X[i+1]]!=S[X[i+1]]){
P[i]=X[i+1],Q[i]=pos[tab[i+1][X[i+1]]];
swap(pos[S[P[i]]],pos[S[Q[i]]]);
swap(S[P[i]],S[Q[i]]);
}
else if(tab[i+1][Y[i+1]]!=S[Y[i+1]]){
P[i]=Y[i+1],Q[i]=pos[tab[i+1][Y[i+1]]];
swap(pos[S[P[i]]],pos[S[Q[i]]]);
swap(S[P[i]],S[Q[i]]);
}
else{
for (int j = 0; j < N; ++j)
if(tab[i+1][j]!=S[j]){
P[i]=j,Q[i]=pos[tab[i+1][j]];
swap(pos[S[P[i]]],pos[S[Q[i]]]);
swap(S[P[i]],S[Q[i]]);
break;
}
}
}
return M;
}
