Codeforces Round #669 (Div. 2) - D. Discrete Centrifugal Jumps
解説
まず、移動パターンは4通りしかありません。
かつ < →番目から一番近い以上のところに行く
かつ < →番目に一番近い以上のところからくる
かつ < →番目から一番近い以下のところに行く
かつ < →番目に一番近い以下のところからくる
なので、各位置においてどこからくるかとどこにいくかは、stackを用いて全体でで求めることができます。
あとは左から右にしか行かないのでDPでよくて、全体の計算量はです