#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define ull unsigned ll
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
///Dremix10's template
template<typename T>
struct SPARSE{
vector<vector<T> > sparse;
vector<int> log;
const int maxPow = 20;
int N;
void init(int n){
sparse.assign(n,vector<T>(maxPow));
log.assign(n+1,0);
N = n;
for(int i = 2;i <= n;i++)
log[i] = log[i/2] + 1;
}
// supports 0-indexing
void build(vector<T> arr){
int i,j;
for(i = 0;i < N ;i++)
sparse[i][0] = arr[i];
for(j = 1;j < maxPow;j++)
for(i = 0;i + (1<<j) <= N;i++)
sparse[i][j] = min(sparse[i][j-1],sparse[i+(1<<(j-1))][j-1]);
}
T query(int l, int r){
int k = log[r-l+1];
return min(sparse[l][k],sparse[r-(1<<k)+1][k]);
}
};
vector<iii>rang[100005];
SPARSE<ll>s[100005];
ll n;
ll h[100005];
void init(int N, int D, int H[]){
n = N;
f(i,0,n){
h[i] = H[i];
}
}
void curseChanges(int U, int A[], int B[]) {
ll u = U;
vector<ii>exo[n];
f(i,0,u){
ll a = A[i],b = B[i];
exo[a].pb(ii(b,i+1));
exo[b].pb(ii(a,i+1));
}
ll last[n];
memset(last,-1,sizeof last);
f(i,0,n){
set<ll>ex;
for(auto x:exo[i]){
if(last[x.F] == -1){
last[x.F] = x.S;
ex.insert(x.F);
}
else{
rang[i].pb(iii(ii(x.S - 1,last[x.F]),h[x.F]));
last[x.F] = -1;
ex.erase(x.F);
}
}
for(auto x:ex){
rang[i].pb(iii(ii(u + 5,last[x]),h[x]));
last[x] = -1;
}
sort(all(rang[i]));
s[i].init(rang[i].size());
vector<ll>vale;
for(auto x:rang[i]){
vale.pb(x.F.S);
}
s[i].build(vale);
}
}
int question(int x, int y, int v) {
ll ans = 1e9;
vector<ii>kame;
ll L;
ll pos = lower_bound(all(rang[x]),iii(ii(v,0),0)) - rang[x].begin();
if(rang[x].size() > 750){
f(j,pos,rang[x].size()){
if(rang[x][j].F.S <= v){
kame.pb(ii(rang[x][j].S,0));
}
}
}
else{
L = pos;
while(1){
ll l = L,r = rang[x].size() - 1;
pos = r + 1;
while(l <= r){
ll mid = (l+r)/2;
if(s[x].query(L,mid) <= v){
r = mid - 1;
pos = min(pos,mid);
}
else{
l = mid + 1;
}
}
if(pos < rang[x].size()){
kame.pb(ii(rang[x][pos].S,0));
}
else{
break;
}
L = pos + 1;
}
}
pos = lower_bound(all(rang[y]),iii(ii(v,0),0)) - rang[y].begin();
if(rang[y].size() > 750){
f(j,pos,rang[y].size()){
if(rang[y][j].F.S <= v){
kame.pb(ii(rang[y][j].S,1));
}
}
}
else{
L = pos;
while(1){
ll l = L,r = rang[y].size() - 1;
pos = r + 1;
while(l <= r){
ll mid = (l+r)/2;
if(s[y].query(L,mid) <= v){
r = mid - 1;
pos = min(pos,mid);
}
else{
l = mid + 1;
}
}
if(pos < rang[y].size()){
kame.pb(ii(rang[y][pos].S,1));
}
else{
break;
}
L = pos + 1;
}
}
sort(all(kame));
f(i,0,(ll)kame.size()-1){
if(kame[i].S != kame[i+1].S){
ans = min(ans,kame[i+1].F - kame[i].F);
}
}
return ans;
}
