How to solve this codeforce problem

Link to the problem is…

Let Hi be a sorted sequence of hi. Let E — set of indices of the last elements of each block. Then for all e in E, first e sorted elements of sequence h_i are equal to the first e elements of the sequence H_j.

So, it is not difficult to notice that the size of E is the answer for the problem.

Firstly, we need to calculate two arrays: prefmax and suffmin, where prefmax(i) — maximum between a1, a2, …, ai, and suffmin(i) — minimum between ai, ai + 1, …, an.

If you want to get the answer, just calculate the number of indices i that prefmax(i)  ≤  suffmin(i) + 1.

Time: O(N)

This is taken from the editorial of the contest. Take a look at it for clearer explanation

it can be solved greedily . if we are at the index ‘i’ and the maximum value of the current block is less than the minimum value with index > i , then we can terminate this block here and start a new block from the next index. So we calculate an array suf[i] which denotes the minimum of all values with index >= i , and we also maintain a variable which has the maximum of current block and then simulate this greedy algorithm. Here is my implementation