#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define IMAX INT_MAX
#define IMIN INT_MIN
#define LMAX LLONG_MAX
#define LMIN LLONG_MIN
#define MOD 1000000007
#define SIR 1000000009
int n, d;
vll vals;
struct cmpVals {
bool operator()(const int x, const int y) const {
if (vals[x] != vals[y]) return vals[x] < vals[y];
return x < y;
}
};
struct sused {
int id, zac, kon = IMAX;
sused* nxt = nullptr;
vector<pair<int, sused*>> prv = {{0, nullptr}};
sused() {};
};
// Bumped size to 600k for absolute safety against bounds issues
const int MAX_NODES = 600005;
sused mem_pool[MAX_NODES];
int pool_sz = 0;
sused* create_sused(int id, int cas) {
sused* nw = &mem_pool[pool_sz++];
nw->id = id;
nw->zac = cas;
nw->kon = IMAX;
nw->nxt = nullptr;
nw->prv.clear();
nw->prv.reserve(2);
nw->prv.push_back({0, nullptr});
return nw;
}
struct saman {
map<int, int> sus;
vector<sused*> adj;
sused* last;
saman() {
auto rnd = create_sused(-1, -1);
adj = {rnd};
sus = map<int, int>();
last = adj[0];
}
bool susedi(int id) {
return (sus.find(id) != sus.end());
}
void pridaj(int id, int cas) {
sused* nw = create_sused(id, cas);
nw->prv.emplace_back(cas, last);
sus[id] = adj.size();
adj.pb(nw);
if (last) last->nxt = nw;
last = nw;
}
void odober(int id, int cas) {
int idx = sus[id];
auto torem = adj[idx];
torem->kon = cas;
if (last == torem) last = torem->prv.back().ss;
auto prvs = torem->prv.back().ss;
auto nxts = torem->nxt;
if (prvs) prvs->nxt = nxts;
if (nxts) nxts->prv.emplace_back(cas, prvs);
sus.erase(id);
}
vi najdi_susedov(int cas) {
vi res;
res.reserve(500);
int b = 0, e = adj.size();
while (e - b > 1) {
auto ono = adj[(b + e) / 2];
if (ono->zac <= cas)
b = (b + e) / 2;
else
e = (b + e) / 2;
}
auto cur = adj[b];
while (cur && cur->id >= 0) {
if (cur->kon > cas) res.pb(cur->id);
b = 0; e = cur->prv.size();
while (e - b > 1) {
int tmp = cur->prv[(b+e)/2].ff;
if (tmp > cas) e = (b+e)/2;
else b = (b+e)/2;
}
cur = cur->prv[b].ss;
}
sort(all(res), cmpVals());
return res;
}
};
vector<saman*> vrch;
void init(int N, int D, int H[]) {
n = N;
d = D;
vals.resize(n);
for (int i = 0; i < n; i++) vals[i] = H[i];
vrch = vector<saman*>(n);
for (int i = 0; i < n; i++) {
vrch[i] = new saman();
}
}
void curseChanges(int U, int A[], int B[]) {
for (int i = 1; i <= U; i++) {
int a = A[i - 1], b = B[i - 1];
if (!vrch[a]->susedi(b)) {
vrch[a]->pridaj(b, i);
vrch[b]->pridaj(a, i);
} else {
vrch[a]->odober(b, i);
vrch[b]->odober(a, i);
}
}
}
int question(int x, int y, int v) {
auto adjx = vrch[x]->najdi_susedov(v);
auto adjy = vrch[y]->najdi_susedov(v);
if (adjx.size() == 0 || adjy.size() == 0) {
return 1000000000;
}
ll best = LMAX;
int ix = 0, iy = 0;
while (ix < adjx.size() && iy < adjy.size()) {
best = min(best, llabs(vals[adjx[ix]] - vals[adjy[iy]]));
if (vals[adjx[ix]] < vals[adjy[iy]]) ix++;
else iy++;
}
return best;
}
