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
Gaurang Gupta: 2013-05-30 13:50:54

Am i supposed to print exactly one digit after . or six? Please help.

Reply : You can print as many digits as you want. The answer should be 10^-6 of the official test data. (i.e. |your_answer-true_answer| < 10^-6)

Last edit: 2013-06-03 17:48:16
Ouditchya Sinha: 2013-05-23 14:04:07

Nice Problem. :)

Arika Saputro: 2013-05-21 06:17:06

i think you must change the example testcase
input :
1
2
output :
1.500000

Reply : It's fine.

Last edit: 2013-06-03 17:54:52
Francky: 2013-04-20 19:50:12

Please tell me an example of error in my solution, thanks in advance. I'm weak with floats, but this problem seems easy to me...
Edit : OK AC, I'm very weak with floats, with some experiments I discovered why I got WA, floats are so strange...

Last edit: 2013-04-20 20:25:56

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