#include "sorting.h"
#include <algorithm>
using namespace std;
int n,R;
int a[200002];
int x[600002],y[600002];
int p[600002],q[600002];
int tested[200002],tester[200002];
int last[200002],where[200002];
bool sorting(){
int i,cnt;
int tmp;
cnt = -1;
for(i=0; i<n; i++) tested[i] = a[i];
for(i=0; i<n; i++) tester[i] = a[i];
for(i=0; i<n; i++) where[tester[i]] = i;
for(i=0; i<R; i++){
swap(tested[x[i]],tested[y[i]]);
}
for(i=0; i<n; i++) last[tested[i]] = i;
for(i=0; i<n; i++){
if(last[i] == i) continue;
cnt++;
if(cnt >= R) return false;
where[tester[x[cnt]]] = y[cnt];
where[tester[y[cnt]]] = x[cnt];
swap(tester[x[cnt]],tester[y[cnt]]);
p[cnt] = where[tested[i]];
q[cnt] = where[tested[last[i]]];
//if(p[cnt] > q[cnt]) swap(p[cnt],q[cnt]);
tmp = last[i];
last[tested[i]] = last[i];
last[i] = i;
swap(tested[i],tested[tmp]);
where[tester[p[cnt]]] = q[cnt];
where[tester[q[cnt]]] = p[cnt];
swap(tester[p[cnt]],tester[q[cnt]]);
}
for(i=cnt+1; i<R; i++) p[i] = q[i] = 0;
return true;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int i,s,e;
s = 0;
e = M;
n = N;
for(i=0; i<N; i++){
a[i] = S[i];
x[i] = X[i];
y[i] = Y[i];
}
while(s != e){
R = (s+e)/2;
if(sorting()) e = R;
else s = R+1;
}
R = (s+e)/2;
sorting();
for(i=0; i<R; i++){
P[i] = p[i];
Q[i] = q[i];
}
return R;
}
