题目描述

给出一个排列。如果其中一个数比它前面的数都大，则称为局部最大值（Local Maxima）。

现在问在一个长度为 $n$ 的随机生成的排列中，期望有多少个数为局部最大值。

输入格式

一行一个正整数 $n$。

输出格式

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

2

1.50000000

提示

长度为 $2$ 的排列共 $2$ 种，为 $(1,2)$ 和 $(2,1)$。前者两个数都为局部最大值，后者仅有第一个数 $2$ 为局部最大值。

数据范围及约定

• 对于 $30\%$ 的数据，$n \leq 10$；
• 对于 $80\%$ 的数据，$n \leq 10^6$；
• 对于 $100\%$ 的数据，$1\leq n < 2^{31}$。