#include<bits/stdc++.h>
using namespace std;
int n, h[1000005];
void init(int N, int D, int H[])
{
n=N;
for(int i=0; i<n; i++) h[i]=H[i];
}
map<pair<int, int>, int> globalmp;
vector<pair<int, int> > st[2000000];
void update(int v, int le, int ri, int be, int en, int st1, int st2)
{
if(le>en || ri<be) return;
if(be<=le && ri<=en)
{
st[v].push_back({st1, st2});
st[v].push_back({st2, st1});
return;
}
int mid=(le+ri)/2;
update(2*v, le, mid, be, en, st1, st2);
update(2*v+1, mid+1, ri, be, en, st1, st2);
}
void curseChanges(int U, int A[], int B[])
{
for(int i=0; i<U; i++)
{
if(A[i]>B[i]) swap(A[i], B[i]);
map<pair<int, int>, int>::iterator it=globalmp.find({A[i], B[i]});
if(it!=globalmp.end())
{
update(1, 0, 2e5+1, (*it).second, i, A[i], B[i]);
globalmp.erase(it);
}
else
{
globalmp[{A[i], B[i]}]=i+1;
}
}
map<pair<int, int>, int>::iterator it=globalmp.begin();
while(it!=globalmp.end())
{
update(1, 0, 2e5+1, (*it).second, U, (*it).first.first, (*it).first.second);
it++;
}
for(int i=0; i<2000000; i++) sort(st[i].begin(), st[i].end());
}
vector<int> vect[2];
void query(int v, int le, int ri, int day, int ch, int id)
{
while(1)
{
int nle=-1, nri=st[v].size();
while(nri-nle>1)
{
int mid=(nle+nri)/2;
if(st[v][mid].first<ch) nle=mid;
else nri=mid;
}
while(nri<st[v].size() && st[v][nri].first==ch)
{
vect[id].push_back(st[v][nri].second);
nri++;
}
if(le==ri) return;
int mid=(le+ri)/2;
if(day<=mid)
{
v=2*v;
ri=mid;
}
else
{
v=2*v+1;
le=mid+1;
}
}
}
int question(int x, int y, int v)
{
vect[0].resize(0);
vect[1].resize(0);
query(1, 0, 2e5+1, v, x, 0);
query(1, 0, 2e5+1, v, y, 1);
int s1=vect[0].size(), s2=vect[1].size(), id1=0, id2=0;
for(int i=0; i<s1; i++) vect[0][i]=h[vect[0][i]];
for(int i=0; i<s2; i++) vect[1][i]=h[vect[1][i]];
sort(vect[0].begin(), vect[0].end());
sort(vect[1].begin(), vect[1].end());
int tekd=1e9;
while(id1<s1 && id2<s2)
{
int dist=vect[0][id1]-vect[1][id2];
if(dist<0)
{
id1++;
dist=-dist;
if(dist<tekd) tekd=dist;
}
else
{
id2++;
if(dist<tekd) tekd=dist;
}
}
return tekd;
}
