explanation of array sharpening codeforces div2 - 616 - problem B

How to know if we can make the prefix [1;k] strictly increasing? We just have to consider the following simple greedy solution: take down values to 0,1,…,k−1 (minimal possible values). It's possible if and only if ai≥i−1 holds in the whole prefix.

Similarly, the suffix [k;n] can be made strictly decreasing if and only if ai≥n−i holds in the whole suffix.

Using these simple facts, we can compute the longest prefix we can make strictly increasing, and the longest suffix we can make strictly decreasing in O(n). Then, we just have to check that their intersection is non-empty.