\(F[x]\) : \(x\leq \min(C)\) を満たすように \(C\) を作るとき，\(\max(C)\) として可能な値の最小値と定義します（不可能ならば \(\infty\)）．初期値は \(F[x]=-\infty\) などとしておきます．求めるべきは \(\min_x (F[x]-x)\) です．

定義から，常に \(F\) は単調増加です．

\((a,b)=(A_i,B_i)\) （ただし \(a\leq b\)）を追加すると，次が起こります．

• \(x\leq a\) に対して \(F[x]=\max(F[x],a)\) と更新
• \(a<x\leq b\) に対して \(F[x]=\max(F[x],b)\) と更新
• \(b<x\) に対して \(F[x]=\infty\) と更新

結局，次の形のクエリ処理を行いながら \(\min_x(F[x]-x)\) を出力せよという問題に帰着できます：

• \(update(p,v)\): \(p\leq x\) に対して \(F[x]=\max(F[x],v)\) と更新．

あとはデータの持ち方を工夫してこのような操作が高速に行えるようにしましょう．

\(F[x]\) を連長圧縮して扱います．つまり，\(F[l]=\cdots=F[r-1]=x\) であるような区間 \((l,r,x)\) をひとつの要素として扱います．実際の実装では組 \((l,F[l])\) を保持するための map などを持てばよいです（実行速度が気になる場合，座圧したあとより高速なデータ構造を使うことも可能）．

\(update(p,v)\) が呼ばれた場合には，

• \(p\) を含むデータを \(p\) が境界になるように分離する（\((l,r,x)\) を \((l,p,x)\) と \((p,r,x)\) にする）
• \(p\leq l\) のデータを小さい方から順に見ていって，\(F[l]\geq v\) になったら終了（単調性が保たれているので終了してよい）．\(v\) 未満であるようなデータをひとつの区間につくりなおす．

するとデータをひとつ余分に見たときには必ずデータ構造の大きさがひとつ減るという感じになるため，データ構造に対する操作は全体で \(O(N)\) 回になります．

答の計算は，連長圧縮した右端における値全体を適切に持つだけでよいのでこれも大きさ \(O(N)\) の適当なデータ構造で容易に行えます（priority queue など）．