Input 
7
1 2 1 1 4 4
Output 
1.0 4.0 5.0 3.5 4.5 5.0 5.0
Input 
12
1 1 2 2 4 4 3 3 1 10 8
Output 
1.0 5.0 5.5 6.5 7.5 8.0 8.0 7.0 7.5 6.5 7.5 8.0