순열의 사전 순 위치

어떤 집합의 순열은 그 집합의 원소가 각각 정확히 한 번씩 나오는 수열이다. 예를 들어 수열 3201은 집합 $\{0, 1, 2, 3\}$의 순열이고, 3이 첫 번째, 2가 두 번째, 0이 세 번째, 1이 마지막에 온다.

두 순열이 처음으로 달라지는 자리를 비교하면 순열을 사전 순으로 늘어놓을 수 있다. 그 자리의 수가 작은 쪽이 앞에 온다. 3201은 3210보다 앞에 온다. 두 순열이 처음 달라지는 세 번째 자리에서 앞의 것은 0이고 뒤의 것은 그보다 큰 1이기 때문이다.

$n = 4$이면 사전에 항목이 24개 들어가고 다음 순서가 된다.

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

정수 $n$ ($1 \le n \le 13$)과 집합 $\{0, 1, 2, \dots, n-1\}$의 순열이 주어진다. 이 순열이 사전에서 몇 번째에 있는지 구하시오.

힌트: 사전의 크기는 $1 \times 2 \times 3 \times \dots \times n$이므로, $n$이 13에 가까우면 사전을 전부 만드는 방법은 너무 느리다.

입력은 두 줄이다.

첫째 줄에 정수 $n$이 주어진다.

둘째 줄에 집합 $\{0, 1, 2, \dots, n-1\}$의 순열이 공백으로 구분되어 주어진다.

순열이 사전에서 몇 번째인지를 정수 하나로 출력한다. 위치는 1부터 세므로, 가장 앞에 오는 순열 $0, 1, 2, \dots, n-1$의 위치는 1이다.