Lexical

A permutation of a set is a sequence in which every element of the set occurs exactly once. For example, the sequence 3201 is a permutation of the set $\{0, 1, 2, 3\}$, where 3 comes first, 2 comes second, 0 comes third and 1 comes last.

Permutations can be ordered in a lexicon by looking at the first position where two of them differ. The one with the smaller number at that position comes first. So 3201 comes before 3210: at the third position, which is the first position where they differ, one has a 0 and the other has the bigger number 1.

For $n = 4$ the lexicon holds 24 entries and runs like this.

0123, 0132, 0213, 0231, 0312, 0321, 1023, 1032, 1203, …, 3201, 3210

Given an integer $n$ ($1 \le n \le 13$) and a permutation of the set $\{0, 1, 2, \dots, n-1\}$, determine the position of that permutation in the lexicon.

Hint: the lexicon has $1 \times 2 \times 3 \times \dots \times n$ entries, so building all of it is too slow once $n$ is close to 13.

The input consists of two lines.

The first line contains the integer $n$.

The second line contains a permutation of the set $\{0, 1, 2, \dots, n-1\}$, with the numbers separated by a space.

Print a single integer, the position of the permutation in the lexicon. Positions are counted from 1, so the first permutation $0, 1, 2, \dots, n-1$ is at position 1.