No.318

$b_i$ はその左右に数値があるもののうちの最大値が入る.

よって, 赤黒木を用意して, 以下の手順で $i = 0$ から順に $b_i$ を計算する.

• 赤黒木に $a_i$ を追加する.
• $b_i$ に赤黒木の最大値をセットする.
• $a_i$ がその数値の右端ならば赤黒木から $a_i$ を削除する.

右端かどうかはあらかじめ計算しておく.