Strictly Increasing Array

csacademy.com

＜問題＞
長さの配列が与えられます。
「を好きな値に書き換える」という操作を考えるとき、
そのような操作を最小で何回行うと、配列を単調増加列とすることができるか。

＜解説＞
全ての要素からindexを引き、（つまり という操作を行う）
その配列で、最大非減少部分列 の長さを求めます。
そのような配列は元の配列で単調増加となっているので、N-(最大非減少部分列の長さ)で答えを求めることができます。
最大非減少部分列はいつもの、長さに対する末尾の値の最小値を二分探索で更新していきましょう。

＜コード＞

int b[1000005];
int main() {

	int n;
	cin >> n;
	vi a(n);
	rep(i, n)cin >> a[i];
	rep(i, n)a[i] -= i;

	
	rep(i, n)b[i] = INF;
	rep(i, n)*upper_bound(b, b + n, a[i]) = a[i];

	P(n-(find(b, b + n, INF) - b));

	return 0;
}

＜感想＞
解説の最大非減少部分列を求めるところが理解不能です。
このindexを引くテクしらなかったんですが、競プロ勢としては常識なんでしょうか・・・。