#include<bits/stdc++.h> typedef long long ll; #define pb push_back #define fr first #define sc second #define endl '\n' using namespace std; #define mid ((left+right)>>1) int n; int h[100023]; map<int,vector<int>>v[100023]; map<int,int>mp[100023]; vector<int>sta[100023]; void init(int N, int D, int H[]){ n=N; for(int i=0;i<n;i++){ h[i]=H[i]; v[i][0]=vector<int>(); } } void f(int tar,int val,int tim){ mp[tar][tim]=val; sta[tar].pb(val); if(sta[tar].size()==10){ set<int>cnt; for(int x:sta[tar]){ if(cnt.count(x))cnt.erase(x); else cnt.insert(x); } sta[tar].clear(); vector<int>&las=(--v[tar].end())->sc; vector<int>&cur=v[tar][tim]; for(int x:las){ if(cnt.count(x)){ cnt.erase(x); continue; } cur.pb(x); } for(int x:cnt){ cur.pb(x); } cnt.clear(); } } void curseChanges(int U, int A[], int B[]){ for(int i=1;i<=U;i++){ int a=A[i-1],b=B[i-1]; f(a,b,i); f(b,a,i); } } _Rb_tree_iterator<pair<const int,vector<int>>>itr1; _Rb_tree_const_iterator<pair<const int,int>>itr; vector<int> cal(int tar,int tim){ itr1=--v[tar].upper_bound(tim); vector<int>&las=itr1->sc; int curtim=itr1->fr; itr=mp[tar].upper_bound(curtim); set<int>cnt; while(itr!=mp[tar].end()&&itr->fr<=tim){ if(cnt.count(itr->sc)){ cnt.erase(itr->sc); } else cnt.insert(itr->sc); itr++; } vector<int>res; for(int x:las){ if(cnt.count(x)){ cnt.erase(x); continue; } res.pb(x); } for(int x:cnt){ res.pb(x); } sort(res.begin(),res.end(),[&](const int &x,const int &y){ return h[x]<h[y]; }); return res; } int question(int x, int y, int v){ int res=1e9; vector<int>a=cal(x,v),b=cal(y,v); int ust=0; for(int x:a){ while(ust<b.size()&&h[b[ust]]<h[x])ust++; if(ust<b.size()){ res=min(res,abs(h[x]-h[b[ust]])); } if(ust-1>=0){ res=min(res,abs(h[x]-h[b[ust-1]])); } } return res; }