A passcode is an arrangement of n integer beads. Consider all distinct arrangements of the same multiset of bead values, listed in lexicographic order and numbered starting from 0. Report the rank (that 0-based position) of the given passcode — equivalently, how many distinct arrangements are lexicographically smaller than it.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the passcode arrangement.
Output format
A single integer: the 0-based lexicographic rank of the arrangement.
Constraints
- 1 ≤ n ≤ 8
- 1 ≤ each value ≤ 1000000