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


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

hide comments
2014-01-11 13:33:46 ishaan
Is this trick some pre-defined formula for solving this question?
I am unable to come up with a formula that fits with all cases.
Edit:Got the pattern

Last edit: 2014-01-11 13:56:19
2013-12-28 11:24:56 Tarun Garg
Think like a lazy man....:D
2013-12-26 17:58:12 Bhavik
good question :)
2013-12-25 06:46:14 Nick
Yes, there's a pattern behind this. You can try.. Btw, thanks @[ _BaDsHah_ ]

I print the answer in single decimal got WA, but normal decimal AC.

Last edit: 2013-12-25 06:50:49
2013-11-09 21:59:19 Akhilesh Anandh
Really good problem.. finally discovered the trick :D
2013-07-02 11:33:55 Alien
agreed hasil

Last edit: 2013-07-02 11:37:04
2013-07-02 11:23:37 Hasil Sharma
KingAditya , can't agree more you only need to know the trick nothing else
2013-06-21 10:48:43 DOT
Some more test cases, please.
2013-06-21 10:28:09 Alien
EASY PROB,if you know the trick
2013-06-01 18:25:22 Chandan Mittal
what will be the o/p for
2

3
4
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.