LOOPEXP  Loop Expectation
Consider the following pseudocode
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 pseudocode 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
Explaination :
for N=2, you can have the following two permutations: [1,2] and [2,1] .
for the first case the if block gets executed 2 times and for the second one the if block gets executed 1 time. So the expected
value is (3)/2 = 1.5
hide comments
nadstratosfer:
20170928 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:
20170626 16:38:07
Nice problem..


sonudoo:
20170208 13:40:35
Enjoyed deriving the formulae :) 

aditya1997:
20160826 08:51:25
use double instead of float.


square1001:
20160816 04:49:55
Easy. Find the logic. 

Archit Jain:
20140820 17:01:18
enjoyed solving it


Anubhav Balodhi :
20140813 20:45:49
Once you work on paper, the problem is simpler... 

SanchitK:
20140324 15:30:14
someone please tell the answer for n=6 

785227:
20140320 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:
20140201 11:18:25
Very nice problem.. :)

Added by:  Aman Gupta 
Date:  20130420 
Time limit:  1s3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own 