#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int findSwapPairs(int N, int arr[], int m, int x[], int y[], int p[], int q[]) {
int n = N;
swap(arr[x[0]], arr[y[0]]);
vector<int> endsUp(n, -1);
for (int i = 0; i < n; i++) {
int lastPlace = i;
for (int j = m-1; j >= i + 1; j--) {
if (x[j] == lastPlace || y[j] == lastPlace) {
lastPlace ^= (x[j] ^ y[j]);
}
}
endsUp[i] = lastPlace;
}
int pos[n], should[n];
for (int i = 0; i < n; i++) {
pos[arr[i]] = i;
should[i] = endsUp[i];
}
for (int i = 0; i < n; i++) {
if (pos[i] == should[i]) {
p[i] = q[i] = 0;
}
else {
p[i] = pos[i];
q[i] = should[i];
swap(arr[pos[i]], arr[should[i]]);
swap(pos[i], pos[arr[pos[i]]]);
}
if (i < n-1) {
swap(arr[x[i + 1]], arr[y[i + 1]]);
swap(pos[x[i + 1]], pos[y[i + 1]]);
}
}
for (int i = n; i < m; i++) {
swap(arr[x[i]], arr[y[i]]);
p[i] = q[i] = 0;
}
//for (int i = 0; i < n; i++) cout << arr[i] << " ";
//cout << '\n';
return m;
}
