Find the first number greater than a given one in an unsorted sequence

Question

Given a sequence of positive integers and an integer M, return the first number in the sequence which is greater than M (or -1 if it doesn't exist).

Example: sequence = [2, 50, 8, 9, 1], M = 3 -> return = 50

O(log n) for each query required (after preprocessing).

I've thought of BSTs, but given an ascending sequence i'd get just a long path, which wouldn't give me O(logn) time...

EDIT: Used structure should be also easy to modify, i.e. it should be possible to replace found element with that given one and repeat searching for another M (everything - apart from preprocessing - O(logn)). And of course it'd be nice, if i could change 'first greater' to 'first smaller' and didn't have to change too much in the algorithm. And if it helps, we may assume all numbers are positive and there are no repetitions.

Answer 1

Create a second array (let it be aux) where for each element i: aux[i] = max { arr[0],arr[1], ... ,arr[i]} (the maximum of all elements with index j <= i in the original array).

It is easy to see that this array is sorted by nature, and a simple binary search on aux will yield the needed index. (It is easy to get with a binary search the first element that is greater then the requested element if the element does not exist).

Time complexity is O(n) pre-processing (done only once) and O(logn) per query.