#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1;
vector<pair<int, int>> v[4 * N];
vector<int> A, B;
int h[N], n, U;
// void build(int x, int tl, int tr) {
// if (tl == tr) {
// return;
// }
// int tm = (tl + tr) / 2;
// build(2 * x, tl, tm);
// build(2 * x + 1, tm + 1, tr);
// }
void dfs(int x, int tl, int tr) {
sort(v[x].begin(), v[x].end());
if (tl == tr)
return;
int tm = (tl + tr) / 2;
dfs(2 * x, tl, tm);
dfs(2 * x + 1, tm + 1, tr);
}
void add(int x, int tl, int tr, int l, int r, int a, int b) {
if (r < tl || l > tr)
return;
if (l <= tl && r >= tr) {
v[x].push_back({a, b});
v[x].push_back({b, a});
return;
}
int tm = (tl + tr) / 2;
add(2 * x, tl, tm, l, r, a, b);
add(2 * x + 1, tm + 1, tr, l, r, a, b);
}
void go(int x, int tl, int tr, int T, int a, int b) {
auto i = lower_bound(v[x].begin(), v[x].end(), make_pair(a, -1)) - v[x].begin();
for (; i < v[x].size(); i++) {
if (v[x][i].first != a)
break;
A.push_back(h[v[x][i].second]);
}
i = lower_bound(v[x].begin(), v[x].end(), make_pair(b, -1)) - v[x].begin();
for (; i < v[x].size(); i++) {
if (v[x][i].first != b)
break;
B.push_back(h[v[x][i].second]);
}
if (tl == tr) {
return;
}
int tm = (tl + tr) / 2;
if (T <= tm)
go(2 * x, tl, tm, T, a, b);
else
go(2 * x + 1, tm + 1, tr, T, a, b);
}
void init(int N, int D, int H[]) {
n = N;
for (int i = 0; i < N; i++) {
h[i] = H[i];
}
}
void curseChanges(int U, int A[], int B[]) {
map<pair<int, int>, int> open;
::U = U;
// build(1, 0, U);
for (int i = 0; i < U; i++) {
if (A[i] > B[i])
swap(A[i], B[i]);
if (open[{A[i], B[i]}]) {
add(1, 0, U, open[{A[i], B[i]}], i, A[i], B[i]);
open[{A[i], B[i]}] = 0;
} else {
open[{A[i], B[i]}] = i + 1;
}
}
for (auto i : open) {
if (i.second) {
add(1, 0, U, i.second, U, i.first.first, i.first.second);
}
}
dfs(1, 0, U);
}
int question(int x, int y, int v) {
int res = 1e9;
go(1, 0, U, v, x, y);
if (A.empty() || B.empty()) {
A.clear();
B.clear();
return res;
}
sort(A.begin(), A.end());
sort(B.begin(), B.end());
// cou t << "X: " << s[x].size() << " Y: " << s[y].size() << " V: " << v << "\n";
for (auto i : A) {
auto r = lower_bound(B.begin(), B.end(), i);
if (r != B.end()) {
res = min(res, abs(i - *r));
}
if (r != B.begin()) {
r--;
res = min(res, abs(i - *r));
}
}
A.clear();
B.clear();
return res;
}
