C. Crazy Dance
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

There are $$$n$$$ dancers on the number line. Each dancer is at an integer coordinate. It is possible for multiple dancers to be at the same location.

During a dance, every dancer moves either $$$1$$$ unit to the left or to the right. They make this decision uniformly at random and independently of the other dancers.

Let's say a dance is crazy, if for all integers $$$x$$$, the number of dancers at position $$$x$$$ stays the same. For example, if the dancers are at positions $$$[1,2,3,2]$$$, and after the dance the positions become $$$[2,1,2,3]$$$, then the dance is crazy. But if the positions instead become $$$[0,3,4,3]$$$, then the dance is not crazy.

What is the maximum probability that the dance is crazy, if you place the dancers optimally?

Input

The only line contains $$$n$$$ ($$$1 \le n \le 40\,000$$$).

Output

The output format is a bit unusual. In particular, let $$$ans$$$ be the desired probability. Then you will need to output $$$\log_2(ans)$$$. If $$$ans = 0$$$, then you should output $$$0$$$.

Your answer will then be considered correct if its absolute or relative error does not exceed $$$10^{-9}$$$. Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-9}$$$.

Examples
Input
4
Output
-3.00000000000000000000
Input
1
Output
0
Note

In the first test, one optimal placement is $$$[1,2,3,2]$$$. We can show this yields a probability $$$ans=\frac{1}{8}$$$.

In the second test, there is only one dancer. It is impossible for the dance to be crazy, so the answer is $$$0$$$ and we output $$$0$$$.