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.)
Line 1: an integer n, the number of readings.
Line 2: n space-separated integers, the readings in arrival order.
n space-separated integers on one line: the lower median after each reading, in arrival order.
Example 1
Input
5 4 1 7 3 2
Expected
4 1 4 3 3
Explanation
Prefixes give medians: [4]->4; [1,4]->1; [1,4,7]->4; [1,3,4,7]->3; [1,2,3,4,7]->3. Output: 4 1 4 3 3.
Example 2
Input
3 5 5 5
Expected
5 5 5
Explanation
Every prefix consists only of 5s, so the lower median is 5 each time.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →