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