#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() {};
};
const int MAX_NODES = 500005;
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.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;
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->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;
}
// int main() {
// int N, D, U, Q;
// std::ios::sync_with_stdio(false); std::cin.tie(NULL);
// std::cin >> N >> D >> U >> Q;
// int *F = new int[N];
// for (int i=0; i<N; i++)
// std::cin >> F[i];
// init(N, D, F);
// int *A = new int[U], *B = new int[U];
// for (int i=0; i<U; i++) {
// std::cin >> A[i] >> B[i];
// }
// curseChanges(U, A, B);
// bool correct = true;
// for (int i=0; i<Q; i++) {
// int X,Y,V,CorrectAnswer;
// std::cin >> X >> Y >> V >> CorrectAnswer;
// int YourAnswer = question(X,Y,V);
// if (YourAnswer != CorrectAnswer) {
// std::cout << "WA! Question: " << i
// << " (X=" << X << ", Y=" << Y << ", V=" << V << ") "
// << "Your answer: " << YourAnswer
// << " Correct Answer: " << CorrectAnswer << std::endl;
// correct = false;
// } else {
// std::cerr << YourAnswer << " - OK" << std::endl;
// }
// }
// if (correct) {
// std::cout << "Correct." << std::endl;
// } else std::cout << "Incorrect." << std::endl;
// return 0;
// }
