#include <bits/stdc++.h>
using namespace std;
struct node {
short val = 0;
//int nextl = -1;
int nextr = -1;
int l = -1, r = -1;
};
struct st {
vector<node> v;
int as;
};
st build (int n) {
int as = 1 << (__lg(n) + 1);
vector<node> v (as*2);
for (int i = as-1; i > 0; i--) {
v[i].l = i*2;
v[i].r = i*2 + 1;
}
return {v, as};
}
pair<int, int> update (st &seg, int id, int d, int i, int lo = 0, int hi = -1) {
if (hi == -1) hi = seg.as;
int nid = seg.v.size();
seg.v.push_back(seg.v[i]);
if (lo == hi-1) {
seg.v[nid].val += d;
return {nid, nid};
}
int mid = (lo + hi) / 2;
int qa, qb;
if (id < mid) {
tie(qa, qb) = update(seg, id, d, seg.v[nid].l, lo, mid);
seg.v[nid].l = qa;
} else {
tie(qa, qb) = update(seg, id, d, seg.v[nid].r, mid, hi);
seg.v[nid].r = qa;
}
seg.v[nid].val = seg.v[seg.v[nid].l].val + seg.v[seg.v[nid].r].val;
return {nid, qb};
}
int query (st &seg, int id, int i, int lo = 0, int hi = -1) {
if (hi == -1) hi = seg.as;
if (lo == hi-1) return i;
int mid = (lo + hi) / 2;
if (id < mid) {
return query(seg, id, seg.v[i].l, lo, mid);
} else {
return query(seg, id, seg.v[i].r, mid, hi);
}
}
int searchl (st &seg, int id, int i, int lo = 0, int hi = -1) {
if (hi == -1) hi = seg.as;
if (lo >= id) return -1;
if (lo == hi-1) {
if (seg.v[i].val > 0) return lo;
else return -1;
}
int mid = (lo + hi) / 2;
int lid = seg.v[i].l;
int rid = seg.v[i].r;
int sol = -1;
if (seg.v[rid].val > 0) {
sol = searchl(seg, id, rid, mid, hi);
}
if (sol == -1 && seg.v[lid].val > 0) {
sol = searchl(seg, id, lid, lo, mid);
}
return sol;
}
int searchr (st &seg, int id, int i, int lo = 0, int hi = -1) {
if (hi == -1) hi = seg.as;
if (hi <= id+1) return -1;
if (lo == hi-1) {
if (seg.v[i].val > 0) return lo;
else return -1;
}
int mid = (lo + hi) / 2;
int lid = seg.v[i].l;
int rid = seg.v[i].r;
int sol = -1;
if (seg.v[lid].val > 0) {
sol = searchr(seg, id, lid, lo, mid);
}
if (sol == -1 && seg.v[rid].val > 0) {
sol = searchr(seg, id, rid, mid, hi);
}
return sol;
}
int n, d;
//vector<int> vh;
vector<int> vhs;
vector<int> vid;
st seg;
vector<vector<pair<int, int>>> vroot; // day - root
int add_friend (int a, int b) {
int root = vroot[a].back().second;
int l = searchl(seg, b+1, root);
int r = searchr(seg, b+1, root);
int nl, nr, ni;
tie(root, nl) = update(seg, l, 0, root);
tie(root, nr) = update(seg, r, 0, root);
tie(root, ni) = update(seg, b+1, 1, root);
seg.v[nl].nextr = b+1;
/*seg.v[nr].nextl = b+1;
seg.v[ni].nextl = l;*/
seg.v[ni].nextr = r;
return root;
}
int rem_friend (int a, int b) {
int root = vroot[a].back().second;
int l = searchl(seg, b+1, root);
int r = searchr(seg, b+1, root);
int nl, nr, ni;
tie(root, nl) = update(seg, l, 0, root);
tie(root, nr) = update(seg, r, 0, root);
tie(root, ni) = update(seg, b+1, -1, root);
seg.v[nl].nextr = r;
//seg.v[nr].nextl = l;
return root;
}
void init(int N, int D, int H[]) {
n = N;
d = D;
vhs = vector<int> (N);
vector<pair<int, int>> vq;
for (int i = 0; i < N; i++) {
vhs[i] = H[i];
vq.push_back({vhs[i], i});
}
sort(vhs.begin(), vhs.end());
sort(vq.begin(), vq.end());
vid = vector<int> (n);
for (int i = 0; i < N; i++) {
vid[vq[i].second] = i;
}
seg = build(n+2);
int root = 1;
int l, r;
tie(root, l) = update(seg, 0, 1, 1);
tie(root, r) = update(seg, n+1, 1, root);
seg.v[l].nextr = n+1;
//seg.v[r].nextl = 0;
vroot = vector<vector<pair<int, int>>> (n, vector<pair<int, int>> {{-1, root}});
}
void curseChanges(int U, int A[], int B[]) {
for (int i = 0; i < U; i++) {
int a = vid[A[i]];
int b = vid[B[i]];
if (seg.v[query(seg, b+1, vroot[a].back().second)].val == 1) {
vroot[a].push_back({i, rem_friend(a, b)});
vroot[b].push_back({i, rem_friend(b, a)});
} else {
vroot[a].push_back({i, add_friend(a, b)});
vroot[b].push_back({i, add_friend(b, a)});
}
}
}
int question(int x, int y, int v) {
int x1 = vid[x];
int y1 = vid[y];
int rootx = (--upper_bound(vroot[x1].begin(), vroot[x1].end(), make_pair(v, 0)))->second;
int rooty = (--upper_bound(vroot[y1].begin(), vroot[y1].end(), make_pair(v, 0)))->second;
int l = query(seg, 0, rootx);
int r = query(seg, 0, rooty);
int sol = 1e9;
int curl = 0;
int curr = 0;
while (seg.v[l].nextr != -1) {
curl = seg.v[l].nextr;
l = query(seg, seg.v[l].nextr, rootx);
if (seg.v[l].nextr == -1) continue;
while (seg.v[r].nextr != -1 && seg.v[r].nextr <= curl) {
curr = seg.v[r].nextr;
r = query(seg, seg.v[r].nextr, rooty);
}
if (curr != 0 && curr != n+1) {
int nsol = vhs[curl-1] - vhs[curr - 1];
sol = min(sol, nsol);
}
if (seg.v[r].nextr != -1 && seg.v[r].nextr != 0 && seg.v[r].nextr != n+1) {
int nsol = abs(vhs[curl-1] - vhs[seg.v[r].nextr - 1]);
sol = min(sol, nsol);
}
}
return sol;
}
