//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
int n, d;
vector<int> h;
vector<vector<array<int, 2>>> a;
vector<vector<array<int, 2>>> op;
vector<vector<vector<int>>> b;
void init(int N, int D, int H[]){
n = N; d = D;
a.resize(n);
b.resize(n);
op.resize(n);
for(int i=0; i<n; i++) h.push_back(H[i]);
vector<int> emp;
for(int i=0; i<n; i++){
a[i].push_back({0, 0});
b[i].push_back(emp);
}
}
void curseChanges(int U, int A[], int B[]){
for(int i=1; i<=U; i++){
op[B[i-1]].push_back({i, A[i-1]});
op[A[i-1]].push_back({i, B[i-1]});
}
for(int i=0; i<n; i++){
vector<int> st;
for(int j=0; j<op[i].size(); j++){
st.push_back(op[i][j][1]);
if(j%100) continue;
vector<int>ar;
sort(st.begin(), st.end(), [&](int x, int y){
if(h[x]!=h[y]) return h[x]<h[y];
return x<y;
});
int k=1;
for(int l=1; l<st.size(); l++){
if(st[l]==st[l-1]) k++;
else{
if(k%2==1){
ar.push_back(st[l-1]);
}
k=1;
}
}
if(k%2==1){
ar.push_back(st.back());
}
a[i].push_back({op[i][j][0], j});
b[i].push_back(ar);
st = ar;
}
}
}
int question(int x, int y, int v){
int posx=lower_bound(a[x].begin(), a[x].end(), (array<int, 2>){v+1, 0})-a[x].begin()-1;
int posy=lower_bound(a[y].begin(), a[y].end(),(array<int, 2>){v+1, 0})-a[y].begin()-1;
vector<int> xx, yy, xr, yr;
for(int i=a[x][posx][1]+1; i<op[x].size()&&op[x][i][0]<=v; i++){
xx.push_back(op[x][i][1]);
}
for(int i=a[y][posy][1]+1; i<op[y].size()&&op[y][i][0]<=v; i++){
yy.push_back(op[y][i][1]);
}
sort(xx.begin(), xx.end(), [&](int x, int y){
if(h[x]!=h[y]) return h[x]<h[y];
return x<y;
});
sort(yy.begin(), yy.end(), [&](int x, int y){
if(h[x]!=h[y]) return h[x]<h[y];
return x<y;
});
int k=1;
for(int l=1; l<xx.size(); l++){
if(xx[l]==xx[l-1]) k++;
else{
if(k%2==1){
xr.push_back(xx[l-1]);
}
k=1;
}
}
if(k%2==1&&xx.size()){
xr.push_back(xx.back());
}
k=1;
for(int l=1; l<yy.size(); l++){
if(yy[l]==yy[l-1]) k++;
else{
if(k%2==1){
yr.push_back(yy[l-1]);
}
k=1;
}
}
if(k%2==1&&yy.size()){
yr.push_back(yy.back());
}
int itx=0, ity=0;
int itrx=0, itry=0;
int ans = 1e9,pe=5000;
while(pe--){
if(itrx>=xr.size() && itx>=b[x][posx].size()) break;
if(itry>=yr.size() && ity>=b[y][posy].size()) break;
int valfirst, valsecond;
int p1, p2;
int check =0;
if(itrx < xr.size() && itx < b[x][posx].size()){
if(xr[itrx] == b[x][posx][itx]){
itrx++; itx++;
check=1;
}
else{
valfirst=min(h[xr[itrx]], h[b[x][posx][itx]]);
if(h[xr[itrx]]<h[b[x][posx][itx]]) p1=0;
else p1=1;
}
}
else if(itrx<xr.size()){
p1=0;
valfirst=h[xr[itrx]];
}
else p1=1, valfirst=h[b[x][posx][itx]];
if(itry < yr.size() && ity < b[y][posy].size()){
if(yr[itry] == b[y][posy][ity]){
itry++; ity++;
check=1;
}
else{
valsecond=min(h[yr[itry]], h[b[y][posy][ity]]);
if(h[yr[itry]]<h[b[y][posy][ity]]) p2=0;
else p2=1;
}
}
else if(itry<yr.size()){
p2=0;
valsecond=h[yr[itry]];
}
else p2=1, valsecond=h[b[y][posy][ity]];
if(check) continue;
ans=min(ans, abs(valfirst-valsecond));
if(p1==0&&p2==0){
if(h[xr[itrx]] < h[yr[itry]]) itrx++;
else itry++;
}
else if(p1==0&&p2==1){
if(h[xr[itrx]] < h[b[y][posy][ity]]) itrx++;
else ity++;
}
else if(p1==1&&p2==0){
if(h[b[x][posx][itx]] < h[yr[itry]]) itx++;
else itry++;
}
else{
if(h[b[x][posx][itx]] < h[b[y][posy][ity]]) itx++;
else ity++;
}
}
return ans;
return 1;
}/*
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;
}
}
cout<<(float)(clock())/1000.0<<"\n";
if (correct) {
std::cout << "Correct." << std::endl;
} else std::cout << "Incorrect." << std::endl;
return 0;
}
*/
