I think this line:

We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i `(1 <= i < n)`

.

Should be:

We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i `(0 <= i < n)`

.

Am I misunderstanding this?