#include "bits/stdc++.h"
using namespace std;
int current_point;
int node;
int link[400010];
int id[400010];
int len[400010];
map <int, int> mp;
set <int> s;
int anc[20][400010];
int dep[400010], dist[400010];
const int logn = 19;
void init()
{
s.clear();
mp.clear();
node = 1;
current_point = 1;
id[1] = 1;
len[1] = 0;
link[1] = -1;
mp[1] = node;
s.insert(1);
}
void path(int a, int sq)
{
current_point += sq;
id[++node] = current_point;
len[node] = sq;
link[node] = a;
mp[current_point] = node;
s.insert(current_point);
int par = mp[*s.lower_bound(a)];
anc[0][node] = par;
dep[node] = dep[par] + 1;
dist[node] = dist[par] + len[par] - (id[par] - a);
for(int i = 1; i <= logn; i++) {
anc[i][node] = anc[i - 1][anc[i - 1][node]];
}
}
int find_node(int x) {
return mp[*s.lower_bound(x)];
}
int lca(int p, int q) {
if(dep[p] > dep[q]) swap(p, q);
for(int i = logn; i >= 0; i--) {
if(dep[q] - (1 << i) >= dep[p]) {
q = anc[i][q];
}
}
if(p == q) return p;
for(int i = logn; i >= 0; i--) {
if(anc[i][p] != anc[i][q]) {
p = anc[i][p];
q = anc[i][q];
}
}
return anc[0][p];
}
int lift(int p, int deep) {
for(int i = logn; i >= 0; i--) {
if(dep[p] - (1 << i) >= deep) {
p = anc[i][p];
}
}
return p;
}
int distance(int p, int q) {
int s = find_node(p);
int t = find_node(q);
int pr = lca(s, t);
int lp, lq;
long long ans = dist[s] + dist[t] - 2 * dist[pr];
ans += len[s] - abs(id[s] - p);
ans += len[t] - abs(id[t] - q);
lp = (s == pr) ? p : link[lift(s, dep[pr] + 1)];
lq = (t == pr) ? q : link[lift(t, dep[pr] + 1)];
ans -= len[pr] - abs(id[pr] - min(lp, lq));
ans -= len[pr] - abs(id[pr] - min(lp, lq));
return ans;
}
int move_up(int x, int up) {
int s = find_node(x);
int nxt_dist = len[s] - abs(id[s] - x);
if(nxt_dist > up) {
return x - up;
}
up -= nxt_dist;
for(int i = logn; i >= 0; i--) {
if(dep[s] < (1 << i)) continue;
int p = anc[i][s];
if(dist[s] - dist[p] < up) {
up -= dist[s] - dist[p];
s = p;
}
}
s = link[s];
return s - up;
}
int dig(int p, int q)
{
int s = find_node(p);
int t = find_node(q);
int pr = lca(s, t);
int lp, lq;
lp = (s == pr) ? p : link[lift(s, dep[pr] + 1)];
lq = (t == pr) ? q : link[lift(t, dep[pr] + 1)];
int tot = distance(p, q);
int med = tot / 2;
if(med <= distance(p, lp)) {
return move_up(p, med);
}
med -= distance(p, lp);
if(med <= abs(lp - lq)) {
if(lp < lq) return lp + med;
else return lp - med;
}
med -= abs(lp - lq);
return move_up(q, distance(q, lq) - med);
}
