A service records latency readings one at a time. After each reading arrives, report the lower median of all readings received so far. For a prefix of length m, sort the values ascending as v[0] <= v[1] <= ... <= v[m-1]; the lower median is the element at 0-based index (m-1) // 2. (For odd m this is the middle value; for even m it is the smaller of the two central values.)
Input format
Line 1: an integer n, the number of readings.
Line 2: n space-separated integers, the readings in arrival order.
Output format
n space-separated integers on one line: the lower median after each reading, in arrival order.
Constraints
- 1 <= n <= 100000
- -1000000000 <= each reading <= 1000000000