#include "island.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100100;
int N, M;
int fval[MAXN];
int floc[MAXN];
int par[MAXN];
vector <int> guys[MAXN];
vector <int> dists[MAXN];
int ndist[MAXN];
int oloc[MAXN];
int nhun[MAXN];
void uni (int left, int right, int now)
{
left = par[left];
right = par[right];
if (left == right) return;
if (guys[left].size() < guys[right].size()) swap (left, right);
dists[left].push_back(now);
for (int guy : guys[right])
{
guys[left].push_back(guy);
par[guy] = left;
}
for (int dist : dists[right])
{
dists[left].push_back(dist);
}
guys[right].clear();
dists[right].clear();
}
void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E){
N = F.size(), M = S.size();
for (int i = 0; i < N; i++)
{
fval[i] = F[i];
floc[fval[i]] = i;
}
for (int i = 0; i < N; i++)
{
guys[i].clear();
dists[i].clear();
guys[i].push_back(i);
par[i] = i;
}
for (int i = M - 1; i >= 0; i--)
{
int l = S[i], r = E[i];
uni (l, r, i + 1);
}
int cp = par[0];
for (int i = 0; i < N; i++)
{
if (i < N - 1)
ndist[i] = dists[cp][i];
oloc[guys[cp][i]] = i;
}
for (int i = 0; i < N; i++)
{
nhun[i] = ndist[i];
for (int j = i; j < i + 100; j++)
nhun[i] = min (nhun[i], ndist[j]);
}
}
int gogo (int x, int y)
{
if (x > y) swap (x, y);
int ans = 1e9;
while (x + 100 < y)
{
ans = min (ans, nhun[x]);
x += 100;
}
for (int i = x; i < y; i++)
ans = min (ans, ndist[i]);
return ans;
}
int Separate(int A, int B)
{
return gogo (oloc[floc[A]], oloc[floc[B]]);
}
