
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. Input The input contains multiple cases. In each case, there is a single integer n (1<=n<=2^311) indicating the number of elements of the permutation. Output Ouput the average number of local maxima in a single line. Accurate the result up to 8 decimal numbers. Sample Input 1 2 Sample Output 1.00000000 1.50000000 Author: FAN, Xiang 