56 - ZOJ Monthly, October 2006 - 1003
For a permutation, we call the element which is larger than any of its successors as "local maxima". Your task is to calculate the average number of local maxima in a random permutaion of n elements.
The input contains multiple cases. In each case, there is a single integer n (1<=n<=2^31-1) indicating the number of elements of the permutation.
Ouput the average number of local maxima in a single line. Accurate the result up to 8 decimal numbers.
Author: FAN, Xiang