#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
struct Node {
int mn, mx, cnt;
Node *l, *r;
Node(int val, int c): mn(val), mx(val), cnt(c), l(nullptr), r(nullptr) {}
Node(Node *ll, Node *rr) {
l = ll, r = rr;
mn = INF, mx = -INF;
if (l && l->cnt) mn = min(mn, l->mn), mx = max(mx, l->mx), cnt = 1;
if (r && r->cnt) mn = min(mn, r->mn), mx = max(mx, r->mx), cnt = 1;
}
};
vector<int> comp;
int idx[100000];
map<int, Node*> persist_roots[100000];
Node* update(Node *node, int pos, int val, int l = 1, int r = comp.size()) {
if (l == r) return (node->cnt + val ? new Node(l, node->cnt + val) : nullptr);
if (!node) node = new Node(0, 0);
int mid = (l + r) / 2;
if (pos > mid) {
if (!node->r) node->r = new Node(0, 0);
Node *ur = update(node->r, pos, val, mid + 1, r);
if (!ur && !node->l) return nullptr;
return new Node(node->l, ur);
}
if (!node->l) node->l = new Node(0, 0);
Node *ul = update(node->l, pos, val, l, mid);
if (!ul && !node->l) return nullptr;
return new Node(ul, node->r);
}
pair<int, int> query(Node *node, int pos, int l = 1, int r = comp.size()) {
if (!node) return {-INF, INF};
if (pos < node->mn) return {-INF, node->mn};
if (pos >= node->mx) return {node->mx, INF};
int mid = (l + r) / 2;
pair<int, int> l_ans = query(node->l, pos, l, mid);
pair<int, int> r_ans = query(node->r, pos, mid + 1, r);
return {max(l_ans.first, r_ans.first), min(l_ans.second, r_ans.second)};
}
void init(int N, int D, int H[]) {
for (int i = 0; i < N; i++) comp.push_back(H[i]);
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
for (int i = 0; i < N; i++) {
idx[i] = lower_bound(comp.begin(), comp.end(), H[i]) - comp.begin() + 1;
persist_roots[i][0] = nullptr;
}
}
set<int> trust[100000];
void curseChanges(int U, int A[], int B[]) {
for (int i = 0; i < U; i++) {
if (trust[A[i]].find(B[i]) == trust[A[i]].end()) {
trust[A[i]].insert(B[i]);
trust[B[i]].insert(A[i]);
persist_roots[A[i]][i + 1] = update(persist_roots[A[i]].rbegin()->second, idx[B[i]], 1);
persist_roots[B[i]][i + 1] = update(persist_roots[B[i]].rbegin()->second, idx[A[i]], 1);
} else {
trust[A[i]].erase(B[i]);
trust[B[i]].erase(A[i]);
persist_roots[A[i]][i + 1] = update(persist_roots[A[i]].rbegin()->second, idx[B[i]], -1);
persist_roots[B[i]][i + 1] = update(persist_roots[B[i]].rbegin()->second, idx[A[i]], -1);
}
}
}
int question(int x, int y, int v) {
Node *x_root = prev(persist_roots[x].upper_bound(v))->second;
Node *y_root = prev(persist_roots[y].upper_bound(v))->second;
int ans = INF;
for (int i = query(x_root, -1).second; i != INF; i = query(x_root, i).second) {
pair<int, int> y_closest = query(y_root, i);
if (y_closest.first != -INF)
ans = min(ans, comp[i - 1] - comp[y_closest.first - 1]);
if (y_closest.second != INF)
ans = min(ans, comp[y_closest.second - 1] - comp[i - 1]);
}
return ans;
}
