Local Maxima

题目描述

给出一个排列。如果其中一个数比它前面的数都大，则称为**局部最大值**（Local Maxima）。 现在问在一个长度为 $n$ 的随机生成的排列中，期望有多少个数为局部最大值。

输入输出格式

输入格式


一行一个正整数 $n$。

输出格式


输出一行一个实数表示答案，保留八位小数。

输入输出样例

输入样例 #1

2

输出样例 #1

1.50000000

说明

长度为 $2$ 的排列共 $2$ 种，为 $(1,2)$ 和 $(2,1)$。前者两个数都为局部最大值，后者仅有第一个数 $2$ 为局部最大值。 ### 数据范围及约定 - 对于 $30\%$ 的数据，$n \leq 10$； - 对于 $80\%$ 的数据，$n \leq 10^6$； - 对于 $100\%$ 的数据，$1\leq n < 2^{31}$。