Running Median Problem

Given a stream of integers, calculate and print the median after each new integer is added to the stream.

Output only the integer part of the median.

Example:

Input:

N = 5  
Stream = [2, 3, 4, 1, 6] 

Output:

2 2 3 2 3

Constraints:

• 0 ≤ N ≤ 10^5
• 1 ≤ ARR[i] ≤ 10^5
• Time Limit: 1 sec