A data structure to find a predecessor in a given range

Question

Given a list of keys, says [2, 6, 4, 9, 3], how can I find the predecessor of an element, with index left to the element only? For example

1. The predecessor of 6 should be 2, not 4, because 4 is on the right of 6.
2. The predecessor of 4 should be 2, not 3.

We know that in a balanced binary search tree, we can find predecessor and successor for given key in O(log n) time complexity, but that is not exactly what I wanted.

I seems like I wanted a data structure with functions from both BST and Interval Tree. But I don't know how to combine them.