Rational Guessing Game

Two players, rin and len, play the following game. Initially, an integer (t) is chosen uniformly at random from the range ([1, n]) (i.e. (l=1) and (r=n)). Then the two players take turns making moves, with rin moving first. In each move, the current player must choose an integer (x) from the current range ([l, r]).

The rules are as follows:

• If \(x = t\), then the game ends immediately and the guessing player loses.
• If \(x < t\), then the range is updated to \([x+1, r]\).
• If \(x > t\), then the range is updated to \([l, x-1]\).

Both players know the rules and all information (except the hidden number \(t\)) and will play optimally to maximize their winning probability. Your task is to determine the probability that rin wins the game, assuming both players play optimally.

In other words, let \(f(l, r)\) be the winning probability for the player whose turn it is when the current range is \([l, r]\). Note that when \(l = r\), the only possible guess is \(x=l\), which immediately loses (i.e. \(f(l, l)=0\)). For a general range \([l, r]\) (with \(m=r-l+1\)), if the current player chooses a guess \(x\), then: \[ f(l, r)=\max_{x\in [l,r]} \left\{ \frac{x-l}{m}\Bigl(1-f(x+1, r)\Bigr) + \frac{r-x}{m}\Bigl(1-f(l, x-1)\Bigr) \right\} \] The final answer is \(f(1, n)\).

inputFormat

The input consists of a single integer n ((1 \leq n \leq 10^3)), which represents the size of the initial range ([1, n]).

outputFormat

Output the winning probability for rin as a floating-point number rounded to 6 decimal places.

sample

1

0.000000