No.270

$A_i$ と $A_{i+1}$ で変化する部分は大きくないことが多いことを利用する.

$A_{i+1}$ を求めるには, まず $A_i$ の後ろから見ていき, 単調増加となる部分列を求める.

そして部分列を反転させ, 部分列のひとつ手前の数値を部分列の中でその数値の次に大きい数値と入れ替えると $A_{i+1}$ となる.

変化する部分は部分列とその手前の数値のみであり, 距離を差分更新すれば $A_{i+1}$ のすべての数値を見る必要がなくなる.