Может быть ты имел в виду a_(n+1) >= a_n? Так я тебе привел монотонный контрпример, где тебе нужно двигать обе границы отрезка, или проебешь элемент целевого множества. O(n^2) или O(n), так вопрос даже не стоит.