Lexicographical order of an array of integers

Question

How to find lexicographical order of an array of N integers(i.e. 1,2,3,...,n) in its permutations in O(n) time?

Ex:- lexicographical order of {2,3,1,4} is 9 in its permutations

• Thilo: Do you know up front which integers make up the set (i.e. only 1,2,3,4 here)? If they can also be {777, 99999, -8888, 5000000} (which yields the same result), I imagine it will be more difficult.
• Thilo: Related: stackoverflow.com/questions/21293906/… stackoverflow.com/questions/7918806/…