Codeforces Round #335 (Div. 1) A. Sorting Railway Cars

配列Aが与えられるので、以下の操作を行ってソートする。

ソートするのに必要な最小の操作回数を求めよ。

ソート完了時には

（左端に飛ばした要素）（移動させなかった要素）（右端に飛ばした要素）

の順に並んでいる。そのため、移動させなかった要素をなるべく多くすれば操作回数を最小化できることが分かる。

移動させなかった要素がソート済みであるためには、要素が連番になっている必要がある。最長の連番部分列を見つけるには、次のようなDPを考えればいい。

dp[i]:=末尾の値がiであるような連番部分列の最長の長さ

自分が提出したコード。DPの更新は簡単にできる。

最初LISかと思ったけど全然違った。