Permutation Generator

Many thanks to Clive Fraser for creating this problem!

The following algorithm generates all of the permutations of the numbers from 1 to N and then stops. It is designed to make the smallest possible change to the permutation in going from one permutation to the next, in the generated sequence. Each step in the sequence involves the swap of two adjacent elements. The algorithm is guaranteed to generate every possible permutation exactly once before stopping.

The algorithm uses direction tags which are temporarily attached to elements in the permutation. All elements in the permutation, except for the number 1, will have a direction tag at some stage during execution of the algorithm. There are two different direction tags. These are L to indicate that an element will be moved to the left at some future step; and R to indicate a future move to the right.

The algorithm always starts with the permutation consisting of the numbers 1 to N in ascending order. All elements except for the number 1 are given an initial direction tag of L. The algorithm to move from one permutation to the next (i.e. for a single step) is described below.

Of all elements which currently have direction tags, we select the largest. This element will be known as the selected element. The selected element is now moved one position in the direction given by its tag. It is exchanged with its immediate neighbour in this direction. If the selected element (in its new position) has no further neighbours in the tag direction, or has an immediate neighbour in the tag direction with a LARGER numeric value, then the selected element has its direction tag removed. Finally we consider every element of the new permutation with a LARGER numeric value than the selected element. If these currently have NO DIRECTION TAG, they are now given a direction tag which is TOWARDS the selected element.

When a permutation is created where none of the elements has a direction tag, the process is complete and all possible permutations have been created.

If we take N = 3 as an example, we need to use the algorithm to create all permutations of the numbers from 1 to 3. This is shown in the diagram below. There are 6 permutations in total, numbered from 1 to 6 in the order of creation. The left side of the diagram shows the list of permutations. The right side of the diagram includes the direction tags to show the algorithm in operation.

1     1 2 3     1  2L 3L
2     1 3 2     1  3L 2L
3     3 1 2     3  1  2L
4     3 2 1     3R 2  1
5     2 3 1     2  3R 1
6     2 1 3     2  1  3

Permutation number 1 shows the numbers 1, 2 and 3 in ascending order. The numbers 2 and 3 (not 1) are given direction tags of L. In executing the first step of the algorithm we identify the selected element 3 (as the largest of the elements with a direction tag). We must move this element one space to the left so elements 3 and 2 exchange places. The selected element (3) has an immediate neighbour (1) in the direction of the tag. Since 1 is not larger than 3, the selected element retains its direction tag. There are no elements larger than 3 so this step is now complete.

The next step starts with permutation number 2. The selected element is again 3, so 3 and 1 exchange places. There are now no more elements to the left of 3 so the selected element loses its direction tag. Permutation 3 is now complete.

In the next step the selected element is 2 (the only element with a direction tag). The elements 2 and 1 are exchanged. The immediate neighbour to the left of 2 is 3. Since 3 is larger than 2, the selected element (2) loses its direction tag. Finally we consider all elements which are larger than the selected element. There is only the element 3. The 3 does not have a direction tag so we give it the tag R which is the direction from 3 towards the selected element (2). Permutation 4 is now complete.

In the next step 3 is once again the selected element and is now moving to the right, so 3 and 2 are exchanged. This completes permutation 5.

In the next step, 3 continues to be the selected element. 3 and 1 are exchanged. There are now no further elements to the right of the selected element, so the 3 loses its direction tag. Permutation 6 is complete. There are now no elements with direction tags, so the algorithm is complete and all permutations have been generated.

The following example shows how the algorithm is used to generate the first 10 permutations for N = 4.

1   1 2 3 4     1  2L 3L 4L
2   1 2 4 3     1  2L 4L 3L
3   1 4 2 3     1  4L 2L 3L
4   4 1 2 3     4  1  2L 3L
5   4 1 3 2     4R 1  3L 2L
6   1 4 3 2     1  4R 3L 2L
7   1 3 4 2     1  3L 4R 2L
8   1 3 2 4     1  3L 2L 4
9   3 1 2 4     3  1  2L 4L
10  3 1 4 2     3  1  4L 2L

Problem Statement

In this problem you will be given a value for N and one particular permutation of the numbers from 1 to N. You are asked to find the position of this permutation in the list of permutations created by the generator.

Input and Output
The first line of the problem will be a single integer T denoting the number of test cases. Each test case will consist of two lines. The first of these will be a single integer N. The second line will contain a particular permutation of the numbers from 1 to N. For each test case you must find the index of this permutation in the list of permutations. Give these answers, separated by spaces, as a single string.

Example:

input:
5
3
2 3 1
4
3 1 4 2
6
5 6 3 2 1 4
8
7 3 2 4 5 8 6 1
10
5 2 4 1 8 7 6 10 3 9

answer:
5 10 452 24131 3197158