#include <bits/stdc++.h>
// #include "grader.cpp"
using namespace std;
struct segtree_arr {
int n;
vector<int> vals;
vector<int> left;
vector<int> right;
segtree_arr() {
}
segtree_arr(int N, int def) {
n = N;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n++;
vals.resize(2*n, -1);
left.resize(2*n, -1);
right.resize(2*n, -1);
for (int i = 0; i < N; i++) {
vals[n+i] = def;
}
for (int i = n-1; i >= 1; i--) {
left[i] = 2*i;
right[i] = 2*i+1;
}
}
int add_node(int v, int l, int r) {
vals.push_back(v);
left.push_back(l);
right.push_back(r);
return vals.size()-1;
}
int set(int idx, int x, int l, int r, int i) {
if (l + 1 == r) {
return add_node(x, -1, -1);
}
int m = (l+r)/2;
if (idx < m) {
return add_node(-1, set(idx, x, l, m, left[i]), right[i]);
} else {
return add_node(-1, left[i], set(idx, x, m, r, right[i]));
}
}
int get(int idx, int l, int r, int i) {
if (l+1 == r) return vals[i];
int m = (l+r)/2;
if (idx < m) return get(idx, l, m, left[i]);
else return get(idx, m, r, right[i]);
}
};
vector<int> heights;
struct cmp {
bool operator()(int x, int y) const {
if (heights[x] == heights[y]) return x < y;
return heights[x] < heights[y];
}
};
vector<set<int,cmp>> adj_sets;
segtree_arr adj;
vector<int> v_roots;
void init(int N, int D, int H[]) {
adj_sets.push_back({});
adj = segtree_arr(N, 0);
v_roots.push_back(1);
heights.resize(N);
for (int i = 0; i < N; i++) heights[i] = H[i];
}
void curseChanges(int U, int A[], int B[]) {
for (int i = 0; i < U; i++) {
int a = A[i], b = B[i];// a--; b--;
set<int,cmp> sa = adj_sets[adj.get(a, 0, adj.n, v_roots.back())];
set<int,cmp> sb = adj_sets[adj.get(b, 0, adj.n, v_roots.back())];
if (sa.find(b) == sa.end()) {
sa.insert(b);
sb.insert(a);
} else {
sa.erase(b);
sb.erase(a);
}
adj_sets.push_back(sa);
adj_sets.push_back(sb);
int tmp_root = adj.set(a, adj_sets.size()-2, 0, adj.n, v_roots.back());
int new_root = adj.set(b, adj_sets.size()-1, 0, adj.n, tmp_root);
v_roots.push_back(new_root);
}
}
int question(int x, int y, int v) {
// cerr << "X = " << x << ", Y = " << y << ", V = " << v << "\n";
set<int,cmp> sx = adj_sets[adj.get(x, 0, adj.n, v_roots[v])];
set<int,cmp> sy = adj_sets[adj.get(y, 0, adj.n, v_roots[v])];
int min_diff = 1e9;
for (int a : sx) {
auto tmp = sy.lower_bound(a);
if (tmp != sy.end()) min_diff = min(min_diff, abs(heights[a] - heights[*tmp]));
if (tmp != sy.begin()) min_diff = min(min_diff, abs(heights[a] - heights[*(--tmp)]));
// for (int b : sy) min_diff = min(min_diff, abs(heights[a] - heights[b]));
}
return min_diff;
}
