Longest “bounded” subsequence

Question

Given a sequence of comparable objects $a_1, a_2, \ldots a_n,$ how quickly can we find the longest subsequence $s$ such that $s_i > s_1$ for $i > 1$? Or equivalently, how quickly can we find

$$ \underset{i}{\arg\max} \; \# \{j \mid a_j > a_i, i < j \le n \} $$

Can it be done in less than $\Omega(n\,\lg n)$ comparisons in the worst case?

A $\Theta(n\,\lg n)$ algorithm is to scan from right to left, inserting each element into a balanced tree, keeping track of how many elements in the tree are larger.

This was inspired by this thread on reddit.