A sensor sends n readings one at a time. After each reading, print the median of all readings received so far. With an even count, the median is the average of the two middle values.
Print every median with exactly one digit after the decimal point.
Constraints
- 1 ≤ n ≤ 100000
- 1 ≤ reading ≤ 10^6
Input and output
- Input
- Line 1: n. Line 2: n positive integers.
- Output
- n lines, one median each (for example `10.0` or `4.5`).
Examples
Input 1
4
5 15 1 3Output
5.0
10.0
5.0
4.0Medians after each reading: 5, (5+15)/2 = 10, 5, (3+5)/2 = 4.
Input 2
3
2 2 2Output
2.0
2.0
2.0All readings equal, so every median is 2.
Show hints
- Keep the smaller half in a max-heap and the larger half in a min-heap.
- Rebalance so the sizes differ by at most one.
Show the explanation
Split the readings into two halves: a max-heap low for the smaller half and a min-heap high for the larger half, with low allowed one extra element. Insert into low, move its top to high (so every value in low ≤ every value in high), and if high grew larger, move its top back. The median is then the top of low (odd count) or the average of both tops (even count). Each reading costs O(log n). Using integer sums and printing .5 or .0 avoids floating-point surprises.
Original UniCircle question. Last reviewed 22 Oct 2026.