Recipe
Limits: 2 sec., 256 MiB
Zenyk wants to surprise Marichka and bake a cake for her. But he is a bad cook, so he decided to search the recipe on the Internet and this is what he found:
Zenyk has \(N\) ingredients. First every \(i\)-th ingredient has \(A_i\) gram. Further in the recipe it is written that every minute Zenyk should take 2 ingredients, mix them and leave exactly half the mixture, and throw away the other half. And to continue until there is only one ingredient left on the table. This will be a base for the cake.
Zenyk also wants to bake a bigger cake to surprise Marichka more. Help Zenyk by determining the maximum weight of the resulting ingredient.
Input
The first line contains one integer \(N\). In the second line there are \(N\) integers \(A_i\).
Output
Output a single number – the maximum weight of the base for the cake.
The answer will be considered correct if its absolute or relative error will not be greater than \(10^{-7}\).
Constraints
\(1 \le N \le 10^5\),
\(1 \le A_i \le 10^5\).
Samples
Input (stdin) | Output (stdout) |
---|---|
3 4 7 4 | 5.500000000 |
Notes
In the first minute, Zenyk mixes the first and third ingredients and receives a new ingredient weighing \({{4+4} \over 2} = 4\). So now Zenyk has an ingredient weighing \(7\) and an ingredient weighing \(4\). Zenyk mixes them and receives a final piece weighing \({{7+4} \over 2} = 5.5\).
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|