Algorithm to maximize $j-i$ subject to $A[j]>A[i]$
As you mention, the candidate $i$s are those who are left-to-right minima, and they form a decreasing sequence. Similarly, the candidate $j$s are right-to-left maxima, and they form an increasing sequence going from right to left (so a decreasing sequence in the usual order). Now imagine keeping two points, one on the left-to-right minima, starting at the leftmost, and another on the right-to-left maxima, starting at the rightmost. Is there a way to traverse both lists in $O(n)$, answering your question on the way?