#include "sorting.h"
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
int findSwapPairs(int N, int SS[], int M, int X[], int Y[], int P[], int Q[]) {
int A[N], pos[N], S[N];
while (true) {
bool F = 1;
for (int i = 0; i < N; ++i)
A[i] = i, S[i] = SS[i];
for (int i = 0; i < M; ++i)
P[i] = Q[i] = 0;
for (int i = M - 1; i >= 0; --i)
swap(A[X[i]], A[Y[i]]);
int r = 0;
for (int i = 0; i < M; ++i) {
swap(S[X[i]], S[Y[i]]);
swap(A[X[i]], A[Y[i]]);
bool f = 1;
for (int j = 1; j < N; ++j)
if (S[j - 1] > S[j])
f = 0;
if (f && i + 1 != M) {
F = 0;
break;
}
for (int j = 0; j < N; ++j)
pos[A[j]] = j;
for (int j = 0; j < N; ++j) {
if (pos[S[j]] != j) {
Q[i] = j, P[i] = pos[S[j]];
++r;
break;
}
}
swap(S[Q[i]], S[P[i]]);
f = 1;
for (int j = 1; j < N; ++j)
if (S[j - 1] > S[j])
f = 0;
if (f && i + 1 != M) {
F = 0;
break;
}
}
bool f = 1;
for (int i = 1; i < N; ++i)
if (S[i - 1] > S[i])
f = 0;
if (F && f) {
return r;
}
--M;
}
}
