A relay squad of n runners is numbered 1 through n. A lineup is an ordering of all n runners. List every possible lineup in lexicographic (dictionary) order of the runner-number sequences and number them starting from 1. Given one particular lineup, output its position (rank) in that list.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, a permutation of 1..n.
Output format
A single integer: the 1-indexed lexicographic rank of the given lineup.
Constraints
- 1 <= n <= 8
- The second line is a permutation of the integers 1..n.