Coding of Permutations

Time limit1sMemory limit128 MB

Summary

The task gives a permutation of 1 to n and asks for its 1-based rank among all permutations in lexicographic order.

Level: Medium4 of 10
Topics: Combinatorics, Math
Solved: No attempts yet

Problem

A permutation $P=(p_1, p_2, \ldots, p_n)$ uses each integer from $1$ to $n$ exactly once. List every permutation of length $n$ in lexicographic order and let $d(P)$ be the position of $P$ in that list. The first one, $(1, 2, \ldots, n)$ , has number $1$ .

Write a program that computes $d(P)$ without generating all permutations of length $n$ . Here $n$ is at most $50$ .

For $n=4$ , the permutations in lexicographic order and their numbers are shown below.

Permutations of length 4 in lexicographic order with their numbers

If $P=(2,3,4,1)$ then $d(P)=10$ , and if $P=(4,2,1,3)$ then $d(P)=21$ .

Input

The input has several lines. Each line holds one query in the form $(n,(p_1,p_2,\ldots,p_n))$ and contains no spaces. The last line holds only $-1$ , and the input ends there. At least one query is given.

Output

Print $d(P)$ for every query on a single line, in the order the queries are given. Separate two values with one comma, and put no space before or after the comma.

Examples2

Example 1
Input
```
(4,(3,2,1,4))
(5,(3,5,1,2,4))
-1
```
Expected output
```
15,67
```
Example 2
Input
```
(4,(2,3,4,1))
(4,(4,2,1,3))
-1
```
Expected output
```
10,21
```