$ (A_i.B_i)のペアで昇順にソートする あるところまでは$ Bをそれから右は$ Aを使うということにする 左端としてあり得る最大値は$ A_iとそれまでのBの最小値の小さい方 右端としてあり得る最小値は$ A_nとそれまでのBの最大値の大きい方 左端に対する右端の値が小さいなら更新する それまでのBの最大値と最小値を$ B_iで…