Mr Brown is the manager of a car company. The company has an assembly line with N workers. The assembly line operates in a fully sequential manner, and every worker has his fixed position, so every worker (except the first and the last) has two neighbors. Mr Brown finds that the workers get too familiar with their neighbors and talk too much during their work. This has harmed the efficiency of the assembly line.

The manager has found a clever way to solve the problem: let the workers rotate their positions daily. The rotation scheme is represented by a permutation P=(P(1),P(2),...P(N)). If a worker is at position i on one day, he will be at position P(i) on the next day. (1<=P(i)<=N). The permutation is the same for each day. Now, the workers don't have fixed neighbors.

Here is the new definition for "neighbors": two workers A and B are neighbors iff there is one day on which A and B are at adjacent positions.

The manager believes that if a worker has many neighbors, he will have little chance to get familiar with each of them, so he will talk less than before.

Mr Brown has devised a permutation plan, and he wants you to evaluate it. Your task is to compute the average number of neighbors a worker will have if his plan is adopted.

There are at most 20 test cases. The first line of each case is the number of workers N (1<=N<=1000). The following line contains N different integers in the range [1,N] which describe the permutation.

A case with N=0 marks the end of input. This case should not be processed.

2
1 2
6
3 5 1 6 2 4
0

1.0000000
3.3333333