Let's use stack. For every element from right to left we will erase elements which are not lower than our current and find the answer when the process stops or understand that is no answer. After that we add current and continue. Every element is added and erased once so it is $$$O(n)$$$ complexity.

Let's build simple Segments Tree with minimums. Now we can recursively do this:

1. Base: if we are in the leaf and value is lower than $$$x$$$, then return the value, else return $$$-1$$$ or $$$INF$$$ or etc.
2. Let m = (l + r) / 2
3. Is minimum on $$$[l; m)$$$ is lower than $$$x$$$?
4. If not, then is minimum on $$$[m; r)$$$ is lower than $$$x$$$?
5. If not $$$2$$$ and not $$$3$$$ then answer does not exist, else let's call it recursively.

We take $$$O(\log{n})$$$ steps because of dividing array by two every step and on every step we make two requests to minimum segment tree, so we have $$$O(n\log^2{n})$$$ solution for both tasks.

Let's understand that we do not need any recursive function except finding minimum in segments tree. Let's watch on every step if our left son has minimum lower than our $$$x$$$ and intersects our search segment than let's call this function recursively from it, else or if answer was not found (for example when minimum is not in intersection) let's call this function with our second child.

This will take $$$O(\log{n})$$$ complexity because of the fact, that we visit no more than two leafs, the very left and if we did not found the answer — the second leaf — the leaf with the answer.