Description

Given a permutation. If an element is larger than all the elements before it, it is called a "Local Maxima".

Now, in a randomly generated permutation of length $n$, find the expected number of elements that are "Local Maxima".

Input Format

A single line containing a positive integer $n$.

Output Format

Output a single real number representing the answer, rounded to eight decimal places.

2

1.50000000

Hint

There are $2$ permutations of length $2$: $(1, 2)$ and $(2, 1)$. In the former, both numbers are "Local Maxima"; in the latter, only the first number $2$ is a "Local Maxima".

Constraints

• For $30\%$ of the testdata, $n \leq 10$.
• For $80\%$ of the testdata, $n \leq 10^6$.
• For $100\%$ of the testdata, $1 \leq n < 2^{31}$.

Translated by ChatGPT 5