ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Contest is over

H. Weird Permutations

Time limit: 0.5 second
Memory limit: 64 MB
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
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.

inputoutput
```4
2 3 1 4
```
```17
```

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
To submit the solution for this problem go to the Problem set: 1174. Weird Permutations