Iterate over all indices i. How do you quickly check the two conditions?

Precompute for each index whether the conditions are satisfied on the left and the right of the index. You can do that with two iterations, from left to right and right to left.