#include <bits/stdc++.h>
using namespace std;
#define int long long
#define map unordered_map
class Intervalac {
public:
int start;
int end; // Exclusive
int center; // == center => right
Intervalac* child_right;
Intervalac* child_left;
vector<int> connections;
Intervalac(int _start, int _end) {
start = _start;
end = _end;
connections = vector<int>();
child_right = nullptr;
child_left = nullptr;
center = (start + end) / 2;
}
void insert(int connection, int _start, int _end) {
if (start == _start && end == _end) {
connections.push_back(connection);
return;
}
if (_start > center) {
if (child_right == nullptr) {
child_right = new Intervalac(center, end);
}
child_right->insert(connection, _start, _end);
return;
}
if (_end <= center) {
if (child_left == nullptr) {
child_left = new Intervalac(start, center);
}
child_left->insert(connection, _start, _end);
return;
}
child_left->insert(connection, _start, center);
child_right->insert(connection, center, _end);
}
vector<int>* get(int obtain) {
if (start + 1 == end) {
return mine();
}
if (obtain >= center) {
if (child_right == nullptr) {
return mine();
}
return mine(child_right->get(obtain));
}
if (child_left == nullptr) {
return mine();
}
return mine(child_left->get(obtain));
}
vector<int>* mine(vector<int>* add_to = nullptr) {
if (add_to == nullptr) {
add_to = new vector<int>();
}
for (int val : connections) {
add_to->push_back(val);
}
return add_to;
}
};
vector<Intervalac*> neighbours;
vector<int> heights;
int number;
void init(int N, int D, int H[]) {
number = N;
neighbours = vector<Intervalac*>();
for (int i = 0; i < N; ++i) {
heights.push_back(H[i]);
}
}
void curseChanges(int U, int A[], int B[]) {
for (int i = 0; i < number; ++i) {
neighbours.push_back(new Intervalac(0, U));
}
map<int, int> active = map<int, int>();
for (int i = 0; i < U; ++i) {
int smaller = min(A[i], B[i]);
int bigger = max(A[i], B[i]);
int value = smaller * 1000000000 + bigger;
if (active.find(value) == active.end()) {
active[value] = i;
} else {
int start = active[value];
neighbours[smaller]->insert(bigger, start, i);
neighbours[bigger]->insert(smaller, start, i);
active.erase(value);
}
}
for (pair<int, int> value : active) {
int start = value.second;
int bigger = value.first % 1000000000;
int smaller = value.first / 1000000000;
neighbours[smaller]->insert(bigger, start, U);
}
}
int question(int X, int Y, int V) {
vector<int>* neighbours_x = neighbours[X]->get(V);
vector<int>* neighbours_y = neighbours[Y]->get(V);
set<int> ordered_heights = set<int>();
for (int neighbour : *neighbours_x) {
ordered_heights.insert(heights[neighbour]);
}
int best = 1000000000;
ordered_heights.insert(LLONG_MAX);
ordered_heights.insert(LLONG_MIN);
for (int neighbour : *neighbours_y) {
int height = heights[neighbour];
int smaller = *ordered_heights.lower_bound(height);
int bigger = *ordered_heights.upper_bound(height);
int this_best = min(height - smaller, bigger - height);
best = min(best, this_best);
}
return best;
}
