ABC247 E - Max Min (500)
全ての区間の組み合わせは$ \mathcal{O}(N^2)なので試すことはできない
$ X,$ Yになっている要素のインデックスを記録しておく
ついでに$ N番目にもあることにする
後ろの方から順に見ていく
$ a_i \gt xなら$ uxをインデックスで更新
$ a_i \lt yなら$ lyをインデックスで更新
それ以外の場合、後ろで最も近い$ x,yのインデックスを取得する
$ (ul,ll)とする
$ \min(ux,ly) - \max(ul,ll)を答えに足す
今見ている地点を左端としたときの右端になりうる範囲になる
それぞれの位置について二分探索をするので$ \mathcal{O}(N log N)