LOOPEXP - Loop Expectation


Consider the following pseudo-code:

int a[1..N];
int max = -1;
for i = 1..N:
    if(a[i] > max):
        max = a[i];

Your task is to calculate the expected number of times the 'if' block of the above pseudo-code executes. The array 'a' is a random permutation of numbers from 1..N chosen uniformly at random.

Input

First line contains t, the number of test cases. t lines follow, each containing N, the number of elements in the array.

1 <= t <= 100

1 <= n <= 100,000

Output

For each test case, output a single decimal. Your answer should be within 10-6 of the correct answer.

Example

Input:
1
2

Output:
1.5

Explanation

For N = 2, you can have the following two permutations: [1, 2] and [2, 1].

In the first case the if block gets executed 2 times, and in the second case the if block gets executed 1 time. So the expected value is (2 + 1) / 2 = 1.5


hide comments
nadstratosfer: 2017-09-28 04:49:55

Found the pattern quickly, spent 1.5h trying to reduce the formula to something computable. Failed, tried what I thought was bruteforce, expected TLE - got AC! Not a good time though so decided to precompute, expected WA due to floats - got AC and best time in Python! Rare case of positive WTF.

sfialok98: 2017-06-26 16:38:07

Nice problem..
Solved using DP and Big Numbers....

sonudoo: 2017-02-08 13:40:35

Enjoyed deriving the formulae :)

aditya1997: 2016-08-26 08:51:25

use double instead of float.
ps: u can print as many digits after . but the answer must be in range of 10^-6 of the official answers

square1001: 2016-08-16 04:49:55

Easy. Find the logic.

Archit Jain: 2014-08-20 17:01:18

enjoyed solving it

Anubhav Balodhi : 2014-08-13 20:45:49

Once you work on paper, the problem is simpler...

SanchitK: 2014-03-24 15:30:14

someone please tell the answer for n=6

785227: 2014-03-20 13:42:46

I found the pattern.. But what does 10^-6 of the correct answer mean ?? I think i am getting WA because of this

Phoenix007: 2014-02-01 11:18:25

Very nice problem.. :)


Added by:Aman Gupta
Date:2013-04-20
Time limit:1s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own