#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mx = 262144;
pair<int, int> pairs[18][mx*2];
int vals[mx];
int compress[mx];
int n;
void init(int N, int D, int H[]) {
n = N;
vector<pair<int, int>> v(N);
for(int i = 0; i < N; i++) v[i] = {H[i], i};
sort(v.begin(), v.end());
for(int i = 0; i < N; i++) {
vals[i] = v[i].first;
compress[v[i].second] = i;
}
}
void init_pairs(int b) {
for(int stt_pos = 0; stt_pos < mx*2; stt_pos += (2<<b)) {
int i1 = stt_pos, i2 = stt_pos + (1<<b);
int e1 = stt_pos + (1<<b);
int e2 = stt_pos + (2<<b);
int cur_pos = stt_pos;
while(i1 != e1 && i2 != e2) {
if(pairs[b - 1][i1] > pairs[b - 1][i2]) {
pairs[b][cur_pos++] = pairs[b - 1][i2++];
} else {
pairs[b][cur_pos++] = pairs[b - 1][i1++];
}
}
while(i2 != e2) {
pairs[b][cur_pos++] = pairs[b - 1][i2++];
}
while(i1 != e1) {
pairs[b][cur_pos++] = pairs[b - 1][i1++];
}
cur_pos = stt_pos;
int oth_pos = stt_pos;
while(oth_pos != e2) {
if(oth_pos != e2 - 1 && pairs[b][oth_pos] == pairs[b][oth_pos + 1]) {
oth_pos += 2;
continue;
}
pairs[b][cur_pos++] = pairs[b][oth_pos++];
}
while(cur_pos != e2) {
pairs[b][cur_pos++] = {mx, mx};
}
}
}
void curseChanges(int U, int A[], int B[]) {
for(int i = 0; i < U; i++) {
int a = compress[A[i]], b = compress[B[i]];
if(a > b) swap(a, b);
pairs[0][i*2] = {a, b};
pairs[0][i*2 + 1] = {b, a};
}
for(int i = U; i < mx; i++) {
pairs[0][i*2] = {mx, mx};
pairs[1][i*2 + 1] = {mx, mx};
}
for(int i = 1; i < 18; i++) init_pairs(i);
}
void add_segment(int b, int pos, int val, vector<int> & v) {
int cur = pos;
for(int delta = (1<<b); delta >= 1; delta >>= 1) {
if(pairs[b][cur + delta].first < val) cur += delta;
}
if(cur != pos || pairs[b][cur].first < val)
cur++;
while(cur != pos + (2<<b)) {
if(pairs[b][cur].first != val) return;
v.push_back(pairs[b][cur].second);
cur++;
}
}
void reduce(vector<int> & v) {
vector<int> tmp;
int last = -1;
for(int i : v) {
if(i == last) {
last = -1;
tmp.pop_back();
} else {
tmp.push_back(i);
last = i;
}
}
swap(v, tmp);
}
int question(int x, int y, int v) {
/*for(int i = 0; i < 16; i++) {
cout << pairs[0][i].first << " " << pairs[0][i].second << endl;
}
cout << endl;
for(int i = 0; i < 16; i++) {
cout << pairs[1][i].first << " " << pairs[1][i].second << endl;
}
cout << endl;
for(int i = 0; i < 16; i++) {
cout << pairs[2][i].first << " " << pairs[2][i].second << endl;
}
cout << endl;
exit(0);*/
x = compress[x];
y = compress[y];
vector<int> v1, v2;
int cur = 0;
for(int b = 17; b >= 0; b--) {
if(cur + (1 << b) <= v) {
add_segment(b, cur*2, x, v1);
add_segment(b, cur*2, y, v2);
cur += (1<<b);
}
}
vector<int> evt;
for(int i : v1) evt.push_back(i*2);
for(int i : v2) evt.push_back(i*2 + 1);
sort(evt.begin(), evt.end());
reduce(evt);
int last1 = -1e9, last2 = -1e9;
int ans = 1e9;
for(auto val : evt) {
if(val & 1) {
last1 = vals[val / 2];
} else {
last2 = vals[val / 2];
}
ans = min(ans, abs(last1 - last2));
}
return ans;
}
