#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,set<pair<int,short>>>mp[100023]; void init(int N, int D, int H[]){ n=N; for(int i=0;i<n;i++){ h[i]=H[i]; mp[i][0]=set<pair<int,short>>(); } } set<pair<int,short>>st; void curseChanges(int U, int A[], int B[]){ for(int i=1;i<=U;i++){ int a=A[i-1],b=B[i-1]; st=(--mp[a].end())->sc; mp[a][i]=st; st=(--mp[b].end())->sc; mp[b][i]=st; if(st.count({h[a],a})){ mp[b][i].erase({h[a],a}); mp[a][i].erase({h[b],b}); } else{ mp[b][i].insert({h[a],a}); mp[a][i].insert({h[b],b}); } } } _Rb_tree_const_iterator<pair<int,short>>itr; int question(int x, int y, int v){ set<pair<int,short>>&a=(--mp[x].upper_bound(v))->sc; set<pair<int,short>>&b=(--mp[y].upper_bound(v))->sc; int res=1e9; for(auto x:a){ itr=b.lower_bound(x); if(itr!=b.end())res=min(res,abs(x.fr-itr->fr)); if(itr!=b.begin()){ itr--; res=min(res,abs(x.fr-itr->fr)); } } return res; }