#P1943. LocalMaxima

LocalMaxima

题目描述

给出一个排列,如果其中一个数比它前面的数都大,则称为 Local Maxima。现在问在一个随机给出的排列中,期望有多少个数为 Local Maxima。

输入格式

一行一个正整数 nn

输出格式

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

2
1.50000000

提示

长度为 22 的排列共 22 种,为 (1,2)(1,2)(2,1)(2,1)。前者两个数都为 Local Maxima,后者仅有第一个数 22 为 Local Maxima。

【数据范围】

对于 30%30\% 的数据,n10n \leq 10

对于 80%80\% 的数据,n106n \leq 10^6

对于 100%100\% 的数据,1n<2311\leq n < 2^{31}