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 for 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.

However, I haven't been able to think of how to solve this issue. Can someone provide hints or a solution to this problem?