There are various $\mathcal O(n \log n)$ or worse solutions, but I'm looking for one that runs in $\mathcal O(n)$, or a proof that none exist.
Given a permutation of 0..N-1, determine the index of that permutation in the lexicographic ordering of all permutations of 0..N-1, in linear time
permutations