#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
int* s;
int* x;
int* y;
int* q;
int* p;
bool isOk(int r)
{
vector<int> change(n);
for (int i = 0; i < n; i++) change[i] = i;
for (int i = 0; i <= r; i++)
{
swap(change[x[i]], change[y[i]]);
}
vector<int> needed(n);
for (int i = 0; i < n; i++)
{
needed[change[i]] = i;
}
vector<int> cur(s, s + n);
vector<int> isOn(n);
for (int i = 0; i < n; i++)
{
isOn[cur[i]] = i;
}
int check = 0;
for (int i = 0; i <= r; i++)
{
swap(cur[x[i]], cur[y[i]]);
swap(needed[x[i]], needed[y[i]]);
isOn[cur[x[i]]] = x[i];
isOn[cur[y[i]]] = y[i];
while (check < n)
{
if (check != needed[isOn[check]])
{
int a = isOn[check];
int b = isOn[needed[isOn[check]]];
swap(cur[a], cur[b]);
isOn[cur[a]] = a;
isOn[cur[b]] = b;
p[i] = a;
q[i] = b;
break;
}
check++;
}
}
for (int i = 1; i < n; i++)
{
if (cur[i] < cur[i - 1]) return false;
}
return true;
}
int bs()
{
int from = 0;
int to = m - 1;
int res = -1;
while (from <= to)
{
int mid = (from + to) / 2;
if (isOk(mid))
{
res = mid;
to = mid - 1;
} else
{
from = mid + 1;
}
}
return res;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n = N;
m = M;
s = S;
x = X;
y = Y;
p = P;
q = Q;
bool alreadyGood = true;
for (int i = 1; i < n; i++)
{
if (s[i] < s[i - 1]) alreadyGood = false;
}
if (alreadyGood) return 0;
int best = -1;
for (int i = 0; i < m; i++)
{
if (isOk(i))
{
best = i + 1;
break;
}
}
return best;
}
