#ifdef LOCAL
#else
#include "sorting.h"
#endif
#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef double db;
int inf = 2e09; ll infll = 2e18; int mod = 1e09+7;
int findSwapPairs(int n, int s[], int m, int x[], int y[], int P[], int Q[]){
vector<int> t(n); //skalowanie
for(int i = 0; i < n; ++i) t[i] = s[i];
sort(t.begin(), t.end());
unordered_map<int, int> mp;
for(int i = 0; i < n; ++i) mp[t[i]] = i;
for(int i = 0; i < n; ++i) s[i] = mp[s[i]];
bool isSorted = 1; // sprawdzenie, czy ciąg jest już posortowany
for(int i = 1; i < n; ++i) if(s[i-1] > s[i]) isSorted = 0;
if(isSorted) return 0;
int l = 1, r = m, mid;
vector<int> where_to_put(n), pos(n), where_in_wtp(n);
while(1){
bool endnow = l == r;
mid = (l+r)>>1;
for(int i = 0; i < n; ++i) t[i] = s[i], pos[s[i]] = i, where_to_put[i] = i;
for(int i = 0; i < mid; ++i) swap(t[x[i]], t[y[i]]), swap(pos[t[x[i]]], pos[t[y[i]]]), swap(where_to_put[x[i]], where_to_put[y[i]]);
for(int i = 0; i < n; ++i) t[i] = s[i], pos[t[i]] = i, where_in_wtp[where_to_put[i]] = i;
/*for(int j = 0; j < n; ++j) printf("%d ", where_to_put[j]);
pn;
for(int j = 0; j < n; ++j) printf("%d ", where_in_wtp[j]);
pn;
pn;*/
int cur = 0, tmp;
for(int i = 0; i < mid; ++i){
//for(int j = 0; j < n; ++j) printf("%d ", t[j]);
//pn;
//printf("%d %d - %d %d\n", where_to_put[where_in_wtp[x[i]]], where_to_put[where_in_wtp[y[i]]], where_in_wtp[x[i]], where_in_wtp[y[i]]);
swap(pos[t[x[i]]], pos[t[y[i]]]);
swap(where_to_put[where_in_wtp[x[i]]], where_to_put[where_in_wtp[y[i]]]);
swap(where_in_wtp[x[i]], where_in_wtp[y[i]]);
swap(t[x[i]], t[y[i]]);
//for(int j = 0; j < n; ++j) printf("%d ", t[j]);
//pn;
while(cur < n){
if(pos[cur] == where_to_put[cur]) ++cur;
else{
P[i] = pos[cur], Q[i] = where_to_put[cur];
tmp = pos[cur];
swap(pos[cur], pos[t[where_to_put[cur]]]);
swap(t[tmp], t[where_to_put[cur]]);
break;
}
}
if(n <= cur) P[i] = 0, Q[i] = 0;
//printf("%d\n", cur);
}
if(endnow) break;
isSorted = 1;
for(int i = 1; i < n; ++i) if(t[i-1] > t[i]) isSorted = 0;
if(isSorted) r = mid;
else l = mid+1;
}
//printf("%d %d\n", n, m);
for(int i = 0; i < l; ++i) if(P[i] > Q[i]) swap(P[i], Q[i]);
return l;
}
#ifdef LOCAL
int main(){
//int T = 1;
//for(++T; --T; ) answer();
return 0;
}
#endif
