Three Romanian programmers developed this new algorithm which generates all the N! permutations with N elements in a specific order, they called the transposition order. The algorithm starts with the permutation 1 2 3 .. N. Then it chooses a
pair of two adjacent elements (that is, two elements which are located on consecutive
positions) and switches them. This way, they get a new permutation. They do the same for this new permutation and they obtain a new one and so on, until all the N! permutations are generated. You realize that the algorithm must be pretty smart in order to generate all the N! permutations exactly once (without repetitions).
Hopefully, your task will not be to write such an algorithm. In fact, you are given the files perm.pas and perm.cpp, which are two implementations of this algorithm (in Pascal and C++). They read the integer N (1 ≤ N ≤ 100) from the keyboard and print to the file perm.txt all the N! permutations, one per line, in the order in which the algorithm generates them.
What you have to do is, given a permutation, to find out its index in the list of permutations generated by the algorithm.
Perm.pas 
Perm.cpp 
const
fileout = 'perm.txt';
MAXN = 100;
var
fout :text;
n, i :integer;
permut :array [1..MAXN] of integer;
position :array [1..MAXN] of integer;
dir :array [1..MAXN] of integer;
procedure PrintPermutation;
begin
for i := 1 to n do
write(fout, ' ', permut[i]);
writeln(fout);
end;
procedure Switch(p1, p2 :integer);
var
xch :integer;
begin
xch := permut[p1];
permut[p1] := permut[p2];
permut[p2] := xch;
position[permut[p1]] := p1;
position[permut[p2]] := p2;
end;
procedure GeneratePermutation(nn :integer);
var ii :integer;
begin
if (nn = n + 1) then
PrintPermutation
else
begin
GeneratePermutation(nn + 1);
for ii := 1 to nn  1 do
begin
Switch(position[nn],
position[nn] + dir[nn]);
GeneratePermutation(nn + 1);
end;
dir[nn] := dir[nn];
end;
end;
begin
readln(n);
for i := 1 to n do
begin
permut[i] := i;
position[i] := i;
dir[i] := 1;
end;
assign(fout, fileout);
rewrite(fout);
GeneratePermutation(1);
close(fout);
end.

#include <stdio.h>
const char *fileout = "perm.txt";
const int MAXN = 100;
FILE *fout;
int n, i;
int permut[MAXN + 1];
int position[MAXN + 1];
int dir[MAXN + 1];
void PrintPermutation()
{
for (i = 1; i <= n; i++)
fprintf(fout, " %d", permut[i]);
fprintf(fout, "\n");
}
void Switch(int p1, int p2)
{
int xch = permut[p1];
permut[p1] = permut[p2];
permut[p2] = xch;
position[permut[p1]] = p1;
position[permut[p2]] = p2;
}
void GeneratePermutation(int nn)
{
int ii;
if (nn == n + 1)
PrintPermutation();
else
{
GeneratePermutation(nn + 1);
for (ii = 1; ii <= nn  1; ii++)
{
Switch(position[nn],
position[nn] + dir[nn]);
GeneratePermutation(nn + 1);
}
dir[nn] = dir[nn];
}
}
int main()
{
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
permut[i] = i;
position[i] = i;
dir[i] = 1;
}
fout = fopen(fileout, "wt");
GeneratePermutation(1);
fclose(fout);
return 0;
}

Input
The first line contains a single integer: N (1 ≤ N ≤ 100). The 2nd line contains N integers separated by blanks. They are the given permutation with N elements.
Output
Print one single integer, which will be the index of the permutation in the list of N! permutations generated by the algorithm described above.
Sample
Notes
Run the 2 given programs for N=4 and you will notice that the permutation 2 3 1 4 will be on the 17th line of the file perm.txt.
Problem Author: Mugurel Ionut Andreica. The Pascal and C++ programs of the three programmers are improved (and, obviously, modified) versions of two programs written by Frank Ruskey (I found them on the Web). So, thanks Frank!
Problem Source: Romanian Open Contest, December 2001