I have a question about a seemingly-simple problem I came up with which I just can't quite solve. In short, given an array $$$A$$$ of integers, I want to support queries and updates:

• Queries give you an index $$$i$$$, and ask for the largest value $$$A[j]$$$ where $$$j \geq i$$$ but $$$A[j] \leq A[i]$$$.
• Updates simply append a value to the array.

My goal is to support both queries and updates in $$$O(\log{n})$$$ time (where $$$n$$$ is the size of $$$A$$$ immediately before the operation) after an at-most $$$O(n\log{n})$$$ preprocessing.

Now, my initial idea was to maintain a BST containing the values in every suffix of $$$A$$$, and specifically use persistent BSTs to save storage (turning $$$O(n^2)$$$ storage into $$$O(n\log{n})$$$ storage needed). Then, given an index $$$i$$$, I would simply query the BST corresponding to the suffix starting at $$$A[i]$$$ to get the answer. However, my idea does not support updates. This is because appending a value to the array changes ALL the suffixes of the array, which in turn would require me to update all the BSTs I had kept for each suffix of the previous array, which would require $$$O(n\log{n})$$$ time.

I had another idea, which was to keep one big BST for the entire array. This BST would be keyed by index, so that for suffix queries, I could just take $$$O(\log{n})$$$ nodes in the BST that correspond to any suffix. Furthermore, updates are easy: simply insert $$$(|A|, \text{new value})$$$ for every new value received. However, the problem here is that by having the BST not be keyed by the array values themselves, I think we lose the ability to efficiently find the maximum value at most a certain value in a subtree, making queries devolve to linear time.

I've spent quite some time thinking about how to turn these ideas into a full solution, but I haven't been able to find a way. Can someone provide hints or a solution to this problem?