There is a list of key vs value pair.size = n. No I have been given a key I have to find the max value from the list such that its key is less than the given key.

If there are q queries I can do this in O(qn). Is there a faster way to do this.