#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define long unsigned long
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define lb lower_bound
#define ub upper_bound
#define sz(v) int((v).size())
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
const int N = 2e5+7;
int n, d, h[N], u, a[N], b[N];
set <int> trusted[N/2];
bool subtask4 = 0;
void init(int N, int D, int H[]) {
n = N; d = D;
int flag = 0;
for (int i = 0; i < N; i++) {
h[i] = H[i];
flag |= h[i];
}
if (flag < 2) {
subtask4 = 1;
}
}
void curseChanges(int U, int A[], int B[]) {
u = U;
for (int i = 0; i < u; i++) {
a[i] = A[i]; b[i] = B[i];
{
auto last = sz(trusted[a[i]]);
trusted[a[i]].insert(b[i]);
if (sz(trusted[a[i]]) == last)
trusted[a[i]].erase(trusted[a[i]].find(b[i]));
}
{
auto last = sz(trusted[b[i]]);
trusted[b[i]].insert(a[i]);
if (sz(trusted[b[i]]) == last)
trusted[b[i]].erase(trusted[b[i]].find(a[i]));
}
}
}
int question(int x, int y, int v) {
vector <pii> friends;
set <int> thief = trusted[x], evil_shaman = trusted[y];
for (int i = u-1; i >= v; i--) {
if (a[i] == x) {
auto last = sz(thief);
thief.insert(b[i]);
if (sz(thief) == last) thief.erase(thief.find(b[i]));
}
else if (b[i] == x) {
auto last = sz(thief);
thief.insert(a[i]);
if (sz(thief) == last) thief.erase(thief.find(a[i]));
}
if (a[i] == y) {
auto last = sz(evil_shaman);
evil_shaman.insert(b[i]);
if (sz(evil_shaman) == last) evil_shaman.erase(evil_shaman.find(b[i]));
}
else if (b[i] == y) {
auto last = sz(evil_shaman);
evil_shaman.insert(a[i]);
if (sz(evil_shaman) == last) evil_shaman.erase(evil_shaman.find(a[i]));
}
}
for (auto to : thief) friends.pb(mp(h[to], x));
for (auto to : evil_shaman) friends.pb(mp(h[to], y));
int mn = 1e9;
sort(all(friends));
int last = -1e9;
for (int i = 0; i < sz(friends); i++) {
auto t = friends[i];
if (t.second == x) last = t.first;
else mn = min(mn, abs(t.first-last));
}
reverse(all(friends));
last = -1e9;
for (int i = 0; i < sz(friends); i++) {
auto t = friends[i];
if (t.second == x) last = t.first;
else mn = min(mn, abs(t.first-last));
}
return mn;
}
