I used range maximum query and binary lifting to solve this problem, the main idea is the following.
If we connect each element to its next greater element with an edge; and those which don’t have a next greater element to a universal root, we get a rooted tree. Observe that the indices of the array act as exit numbers in the rooted tree.
Now the queries become, given the two exit numbers, find the maximum length of a chain.
Now the nodes between two exit numbers contain some(possibly zero) entire subtrees and at most one partial subtree. We use Range Maximum query for the entire subtrees and Binary Lifting for the partial subtrees.