Lexicographic Rank of a Permutation

Uim has delivered gifts to N girls following a certain order. The order in which the gifts were delivered can be represented as a permutation of 1, 2, …, N. Now, Uim is curious to know the lexicographic rank of his chosen permutation among all possible permutations of 1,2,...,N.

The lexicographic rank (or order) of a permutation is defined as its position in the sorted list of all permutations when ordered lexicographically. The first position is considered to be 1.

For example, consider N = 3:

• The permutation [1, 2, 3] is the lexicographically smallest, so its rank is 1.
• The permutation [3, 2, 1] is the lexicographically largest, so its rank is 6 (since 3! = 6).
</p>

The ranking formula can be expressed in \( \LaTeX \) as follows:

[ \text{rank} = 1 + \sum_{i=0}^{N-1} \left(\text{number of unused elements less than } a_i\right) \times (N-i-1)! ]

inputFormat

The input consists of two lines. The first line contains a positive integer N, which is the number of girls. The second line contains N integers, representing the permutation of 1, 2, ..., N in the order Uim delivered the gifts.

outputFormat

Output a single integer, which is the lexicographic rank of the given permutation (1-indexed).

sample

3
1 2 3

1