#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int n, d;
vector<int> h;
void init(int N, int D, int H[]) {
n=N,d=D;
for(int i=0; i<n; ++i) h.push_back(H[i]);
}
int M = 200'010, C = 50;
vector<set<pair<int, int>>> g(M);
vector<vector<pair<int, int>>> changes(M, vector<pair<int, int>>(1));
vector<vector<set<pair<int, int>>>> saves(M, vector<set<pair<int, int>>>(1));
vector<vector<int>> times(M, vector<int>(1,0));
void snapshot(int v) {
/*vector<int> e;
for(auto x : g[v]) e.push_back(x);
saves[v].push_back(e);*/
saves[v].push_back(g[v]);
}
vector<int> odzysk(int v, int t) {
int it = upper_bound(times[v].begin(), times[v].end(), t) - times[v].begin() - 1;
set<pair<int, int>> res = saves[v][it/C];
int s = C*(it/C);
for(int i=s+1; i<=it; ++i) {
auto[a,b] = changes[v][i];
if(b==-1) res.erase({h[a], a});
else res.insert({h[a], a});
}
vector<int> ans; for(auto x : res) ans.push_back(x.first);
return ans;
}
void curseChanges(int U, int A[], int B[]) {
for(int i=0; i<U; ++i) {
int a = A[i]; int b = B[i];
if(g[a].find({h[b], b})==g[a].end()) {
g[a].insert({h[b], b});
g[b].insert({h[a], a});
changes[a].push_back({b, 1});
changes[b].push_back({a, 1});
} else {
g[a].erase({h[b], b});
g[b].erase({h[a], a});
changes[a].push_back({b, -1});
changes[b].push_back({a, -1});
}
if((changes[a].size()%C) == 1) {
snapshot(a);
}
if((changes[b].size()%C) == 1) {
snapshot(b);
}
times[a].push_back(i+1);
times[b].push_back(i+1);
}
}
int question(int X, int Y, int V) {
vector<int> v1 = odzysk(X, V);
vector<int> v2 = odzysk(Y, V);
// for(auto x : v1) cout << x << " "; cout << "\n";
// for(auto x : v2) cout << x << " "; cout << "\n";
if(v1.size()==0 || v2.size()==0) return 1e9;
int idx = 0;
int best = 1e9;
for(auto x : v1) {
while(idx < v2.size()-1 && v2[idx+1] < x) idx++;
best = min(best, abs(x - v2[idx]));
if(idx < v2.size() - 1) best = min(best, abs(x - v2[idx+1]));
}
return best;
}
