#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAX_N=1e5+5; int H[MAX_N]; int N; int D; int d=50; vector<vector<pair<int, set<int>>>> changes(MAX_N, vector<pair<int, set<int>>> (1)); void init(int NN, int DD, int HH[]){ N=NN; D=DD; for(int i=0; i<N; i++) H[i]=HH[i]; for(int i=0; i<N; i++){ changes[i][0].first=0; changes[i][0].second.clear(); } } vector<vector<pair<int, int>>> upd(MAX_N); void curseChanges(int UU, int AA[], int BB[]){ for(int i=0; i<UU; i++){ upd[AA[i]].push_back({i+1, BB[i]}); upd[BB[i]].push_back({i+1, AA[i]}); } for(int i=0; i<N; i++){ for(int r=d; (int)upd[i].size()>=r; r+=d){ changes[i].push_back(changes[i][changes[i].size()-1]); changes[i][r/d].first=upd[i][r-1].first; for(int j=r-d; j<r; j++){ //add all updates int u=upd[i][j].second; if((changes[i][r/d].second).count(u)){ changes[i][r/d].second.erase(u); } else changes[i][r/d].second.insert(u); } } } } set<int> query(int p, int day){ int s=upd[p].size(); int r=0; //binary search here int a=0, b=changes[p].size()-1; if(changes[p][b].first<=day){ r=b; } else{ while(a+1<b){ int c=(a+b)/2; if(changes[p][c].first<=day){ a=c; } else b=c; } r=a; } set<int> ans=changes[p][r].second; for(int t=r*d; t<upd[p].size() && upd[p][t].first<=day; t++){ int u=upd[p][t].second; if(ans.count(u)){ ans.erase(u); } else ans.insert(u); } return ans; } int question(int x, int y, int v){ //find the sets set<int> ans1=query(x, v), ans2=query(y, v); if(ans1.size()==0 || ans2.size()==0) return 1e9; vector<ll> h1; vector<ll> h2; for(int r : ans1){ h1.push_back(H[r]); } for(int r : ans2){ h2.push_back(H[r]); } h2.push_back(-1e9); h2.push_back(2e9); sort(h1.begin(), h1.end()); sort(h2.begin(), h2.end()); ll m=1e9; for(int i=0, e=0; i<h1.size();){ if(h2[e+1]<h1[i]){ e++; continue; } m=min(m, h1[i]-h2[e]); m=min(m, h2[e+1]-h1[i]); i++; } return m; }