Number of permutation

Given a permutation of $n$ numbers from $1$ to $n$. Find its number in the lexicographic order.

Input

The first line contains the integer $n(1\le n\le 12)$. The next line contains the permutation of $n$ numbers.

Output

Print the permutation number in lexicographical order.

Examples