Find Median from a Data Stream
Design a structure that supports adding numbers and finding the median in a continuous data stream.
Input format
The first line contains N. The second line contains N space-separated integers.
Output format
After each element, print the median so far (for even counts, the lower of the two middle values).
Constraints
- Values fit in a 64-bit signed integer
- Trailing whitespace and a trailing newline are ignored by the judge
Read from stdin, write to stdout. Sample cases below show the exact format.
Sample cases
Example 1
Input
5
1 2 3 4 5Expected output
1 1 2 2 3Example 2
Input
3
1 2 3Expected output
1 1 2