场了，好像和官方题解做法不一样，来写一写。
我们考虑直接维护，设 f_i 表示当序列的 \min 为 i 时，\max 的最小值，不断维护增加一对 a,b 后的 f。这里钦定 a\le b。
首先 \forall i>b，不可能存在 \min=i，于是全部 f_i\to \inf。然后 \forall i>a\wedge f_i<b，i 不变就只能选 b，于是 f_i\to b。f_i<a 的也类似，全部 f_i\to a。
然后对于以 a,b 为 \min 的，显然就是查询一段后缀的 f_i 最小值，然后赋值给 f_a,f_b。
现在已经可以直接做了，但是不妨再多做一点观察。不难得到一个结论：对于 f_i\not=\inf 的 i，f_i 单调不降。证明可以直接从上面的操作得到，也可以考虑，若 f_j<f_i,j>i，则考虑用 f_j 的选法，然后将 f_i 对应的最小值的位置变成 i，此时显然有 f_i\le f_j。
于是上述操作就变成了：区间二分 f_i>k 的 i，区间推平，单点修改。已经可以用简单一点的线段树维护了。
但是还可以更简单一点。不难发现有值的位置不多，于是考虑用一个 set 维护 (f_i,i) 的 pair，同时维护 f_i-i 的答案集合。
首先 >b 的部分直接 erase，同时记录这部分中的 mn=\min f_i，插入 (mn,b)。
最后 $f_i<a$ 的部分也是一样，二分然后删掉 $f_i<a$ 的，插入 $(a,mx)$。
总的时间复杂度是 $O(n\log n)$。还有若干细节，比如都要使用 multiset，并且上述插入 $(mn,a)$ 或 $(mn,b)$ 时，如果不存在合法的 $mn$ 就不能插入，否则会影响 $f_i$ 的单调性。
code：
```cpp
int n,m,a[N],b[N];
multiset<pii> st;
multiset<int> ans;
void Yorushika(){
read(n);
rep(i,1,n){
read(a[i]);
}
rep(i,1,n){
read(b[i]);
}
st.emplace(a[1],a[1]);
st.emplace(b[1],b[1]);
ans.insert(0),ans.insert(0);
puts("0");
rep(i,2,n){
if(a[i]>b[i]){
swap(a[i],b[i]);
}
int mn=inf;
while(st.size()&&(--st.end())->se>=b[i]){
auto it=(--st.end());
ans.erase(ans.find(it->fi-it->se));
mn=min(mn,it->fi);
st.erase(it);
}
if(mn<inf){
ans.insert(mn-b[i]);
st.emplace(mn,b[i]);
}
mn=inf;
auto it=st.lower_bound(Mp(b[i],0));
if(it!=st.begin()){
it--;
int p=0;
while(it->se>=a[i]){
if(!p){
p=it->se;
}
ans.erase(ans.find(it->fi-it->se));
mn=min(mn,it->fi);
it=st.erase(it);
if(it==st.begin()){
break;
}
it--;
}
if(p){
st.emplace(b[i],p);
ans.insert(b[i]-p);
}
}
if(mn<inf){
ans.insert(mn-a[i]);
st.emplace(mn,a[i]);
}
it=st.lower_bound(Mp(a[i],0));
if(it!=st.begin()){
it--;
int p=0;
while(1){
if(!p){
p=it->se;
}
ans.erase(ans.find(it->fi-it->se));
it=st.erase(it);
if(it==st.begin()){
break;
}
it--;
}
if(p){
st.emplace(a[i],p);
ans.insert(a[i]-p);
}
}
printf("%d\n",*ans.begin());
}
}
signed main(){
int t=1;
//read(t);
while(t--){
Yorushika();
}
}
```