Draw a Cartesian tree for the sequence 18, 21, 4, 25, 19, 20, 22, 24, 6, 11, 2, 10, 13, 17. In the tree, indicate the pair of nodes such that a lowest common ancestor query for this pair would correspond to a range minimum query for the subsequence from 24 to 13.
List the nodes in the tree you drew for the previous problem, in the order given by an Euler tour of the tree. Each node should be listed as a pair (depth,value); some nodes should appear more than once in your list. Indicate the pair of positions in the list that would correspond to the LCA query from your previous answer.
In the sequence of depths of nodes in a Cartesian tree, the first depth is zero and each depth differs from the previous one by either $+1$ or $-1$, so if the the whole sequence of depths has length $n$, it can be encoded by a sequence of $n-1$ symbols, each of which is either "+" or "-", indicating the change from one depth to the next. Give a subsequence of "+" and "-" symbols that cannot occur (consecutively) within this sequence, and explain why it cannot occur.