http://codeforces.com/contest/1437/problem/E の部分問題を考えます
概要としては，ある整数列 $a$ が与えられ，「要素を一つ選び，任意の整数に置き換える」という操作を繰り返して $a$ を狭義単調増加な数列に変えるために必要な操作回数の最小値を求める問題です
例えば $a = \{3, 4, 4, 7, 9, 8, 10, 11\}$ なら三回の操作で $a = \{3, 4, 5, 7, 8, 9, 10, 11\}$ とできてこれが最小回数です
自明な考察としてそのまま（狭義） $LIS$ をとってそれ以外に対して操作をするということが考えられますが，これだとうまくいきません．理由は $a_i$ を $x$ に変更すると狭義単調増加な状態を保つために， $a_{i - 1} < x$ と $a_{i + 1} > x$ という制約がつくことになってこれを考慮できないからです．上の例だと $LIS$ の一つをとってそれ以外を $?$ で置き換えると $\{3, 4, ?, 7, 9, ?, 10, 11\}$ になりますが二個目の $?$ に入る数は存在しません
そこで $b_i = a_i - i$ となる数列 $b$ を考え， $a$ が狭義単調増加であることと $b$ が広義単調増加であることが同値であることを利用します．数列 $b$ の上では各要素同士の距離を考慮しなくてよくなるので，数列 $b$ で（広義） $LIS$ をとれば答えが分かります．上の例だと $b = \{3, 3, 2, 4, 5, 3, 4, 4\}$ となって $\{3, 3, ?, 4, ?, ?, 4, 4\}$ などがとれて，この $?$ が適当な数で置き換えられないということはありえません
