#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
using namespace std;
using ll = long long;
const ll N = 2e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 , mod = 1e9+7;
int n , d , t , h[N] , a[N] , b[N];
set<pair<int,int>> st[N*4];
void init(int N, int D, int H[]) {
n = N; d = D;
for(int i = 0; i < N; i++) h[i] = H[i];
}
void upd(int v, int tl , int tr , int l , int r , int x , int y){
if(l <= tl && tr <= r){
st[v].insert({x,h[y]});
st[v].insert({y,h[x]});
return;
}
if(tl > r || tr < l) return;
int tm = (tl+tr) >> 1;
upd(v*2,tl,tm,l,r,x,y);
upd(v*2+1,tm+1,tr,l,r,x,y);
}
int ans = 1e9;
set<pair<int,int>> ob;
void get(int v, int tl , int tr , int pos , int x , int y){
auto it = st[v].lower_bound({x,0});
while(it != st[v].end() && it->F == x){
int S = it->S;
auto it2 = ob.lower_bound({S,0});
if(it2 != ob.end()){
if(it2->S != 0){
ans = min(ans , abs(it2->F-S));
}
}
if(it2 != ob.begin()){
it2--;
if(it2->S != 0){
ans = min(ans , abs(it2->F-S));
}
}
ob.insert({S,0});
it++;
}
auto it1 = st[v].lower_bound({y,0});
while(it1 != st[v].end() && it1->F == y){
int S = it1->S;
auto it2 = ob.lower_bound({S,0});
if(it2 != ob.end()){
if(it2->S != 1){
ans = min(ans , abs(it2->F-S));
}
}
if(it2 != ob.begin()){
it2--;
if(it2->S != 1){
ans = min(ans , abs(it2->F-S));
}
}
ob.insert({S,1});
it1++;
}
if(tl == tr) return;
int tm = (tl+tr) >> 1;
if(pos <= tm){
get(v*2,tl,tm,pos,x,y);
} else {
get(v*2+1,tm+1,tr,pos,x,y);
}
}
void curseChanges(int U, int A[], int B[]) {
t = U;
for(int i = 0; i < t; i++){
a[i] = A[i];
b[i] = B[i];
}
map<pair<int,int>,int> mp;
for(int i = 0; i < t; i++){
if(mp[{a[i],b[i]}] == 0){
mp[{a[i],b[i]}] = i+1;
mp[{b[i],a[i]}] = i+1;
} else {
int mx = mp[{a[i],b[i]}];
upd(1,0,t,mx-1,i-1,a[i],b[i]);
mp[{a[i],b[i]}] = 0;
mp[{b[i],a[i]}] = 0;
}
}
for(int i = 0; i < t; i++){
if(mp[{a[i],b[i]}] > 0){
int mx = mp[{a[i],b[i]}];
upd(1,0,t,mx-1,t,a[i],b[i]);
mp[{a[i],b[i]}] = 0;
mp[{b[i],a[i]}] = 0;
}
}
}
int question(int x, int y, int v) {
ob.clear();
ans = 1e9;
get(1,0,t,v,x,y);
return ans;
}
// int main() {
// int N, D, U, Q;
// cin >> N >> D >> U >> Q;
//
// int *F = new int[N];
// for (int i=0; i<N; i++)
// cin >> F[i];
//
// init(N, D, F);
//
// int *A = new int[U], *B = new int[U];
// for (int i=0; i<U; i++) {
// cin >> A[i] >> B[i];
// }
// curseChanges(U, A, B);
//
// for (int i=0; i<Q; i++) {
// int X,Y,V;
// cin >> X >> Y >> V;
// int YourAnswer = question(X,Y,V);
// cout << YourAnswer << "\n";
// }
// return 0;
// }
