ZOJ Problem Set - 2766
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
Source: ZOJ Monthly, October 2006