#include "sorting.h"
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
const int maxN = 200'000;
int N;
vector<int> S(maxN);
int M;
int* X;
int* Y;
int* P;
int* Q;
vector<int> T(maxN);
vector<bool> visit(maxN);
int binary_search(int l, int r)
{
// cerr << "search " << l << ' ' << r << '\n';
if(l == r)
{
vector<int> act1, act2;
T = S;
for(int j = 0; j < l; j++)
swap(T[ X[j] ], T[ Y[j] ]);
// cerr << "final: ";
// for(int i = 0; i < N; i++) cerr << T[i] << ' ';
// cerr << '\n';
vector<int> num1, num2;
for(int i = 0; i < N; i++)
{
int u, v;
u = i;
v = T[u];
// cerr << u << v << '\n';
while(1)
{
if(u == v) break;
swap(T[u], T[v]);
act1.push_back(u);
act2.push_back(v);
num1.push_back(T[u]);
num2.push_back(T[v]);
// cerr << "act swap " << u << ' ' << v << '\n';
u = T[u];
v = T[u];
}
}
vector<int> real(N);
for(int i = 0; i < N; i++) real[i] = i;
vector<int> Z(N);
for(int i = 0; i < N; i++) Z[i] = S[i];
vector<int> Zpos(N);
for(int i = 0; i < N; i++) Zpos[ Z[i] ] = i;
for(int j = 0; j < l; j++)
{
swap(Z[ X[j] ], Z[ Y[j] ]);
swap(Zpos[ Z[ X[j] ] ], Zpos[ Z[ Y[j] ] ]);
swap(Z[ Zpos[ num1[j] ] ], Z[ Zpos[ num2[j] ] ]);
swap(Zpos[ num1[j] ], Zpos[ num2[j] ]);
P[j] = Zpos[ num1[j] ];
Q[j] = Zpos[ num2[j] ];
}
// for(int j = l-1; j >= 0; j--)
// {
// // cerr << "j = " << j << '\n';
// // cerr << act1[j] << ' ' << act2[j] << '\n';
//
// // for(int i = 0; i < N; i++) cerr << real[i] << ' ';
// // cerr << '\n';
// // cerr << "done\n";
//
// P[j] = real[ act1[j] ];
// Q[j] = real[ act2[j] ];
// swap(real[ X[j] ], real[ Y[j] ]);
// }
// cerr << "sequence after unadjusted sorting: ";
// for(int i = 0; i < N; i++) cerr << T[i] << ' ';
// cerr << '\n';
vector<int> fin = S;
for(int j = 0; j < l; j++)
{
swap(fin[ X[j] ], fin[ Y[j] ]);
swap(fin[ P[j] ], fin[ Q[j] ]);
}
// cerr << "sequence after sorting: ";
// for(int i = 0; i < N; i++) cerr << fin[i] << ' ';
// cerr << '\n';
return l;
}
else
{
int m = (l+r)/2;
T = S;
for(int j = 0; j < m; j++)
{
swap(T[ X[j] ], T[ Y[j] ]);
}
for(int i = 0; i < N; i++) visit[i] = 0;
int ct = 0;
for(int i = 0; i < N; i++)
{
if(visit[i]) continue;
ct++;
visit[i] = 1;
for(int j = T[i]; j != i; j = T[j])
visit[j] = 1;
}
if(N - ct <= m)
return binary_search(l, m);
else
return binary_search(m+1, r);
}
}
int findSwapPairs(int N_, int S_[], int M_, int X_[], int Y_[], int P_[], int Q_[])
{
N = N_;
for(int i = 0; i < N; i++) S[i] = S_[i];
M = M_;
X = X_;
Y = Y_;
P = P_;
Q = Q_;
return binary_search(0, M);
}
