Find Median from Data Stream

Given an array of integers nums representing a data stream, process the numbers one by one and find the median of all elements seen so far after each insertion.

The median is the middle value in an ordered list. If the list size is even, the median is the average of the two middle values.

Return an array of medians — one after each number is added to the stream.

Examples

Input: nums = [1, 2, 3]

Output: [1, 1.5, 2]

Explanation:

• After adding 1: list = [1], median = 1
• After adding 2: list = [1, 2], median = (1 + 2) / 2 = 1.5
• After adding 3: list = [1, 2, 3], median = 2

Input: nums = [5, 2, 8]

Output: [5, 3.5, 5]

Explanation:

• After adding 5: list = [5], median = 5
• After adding 2: list = [2, 5], median = (2 + 5) / 2 = 3.5
• After adding 8: list = [2, 5, 8], median = 5

Input: nums = [6, 10, 2, 6, 5]

Output: [6, 8, 6, 6, 6]

Explanation:

• After adding 6: [6], median = 6
• After adding 10: [6, 10], median = 8
• After adding 2: [2, 6, 10], median = 6
• After adding 6: [2, 6, 6, 10], median = 6
• After adding 5: [2, 5, 6, 6, 10], median = 6

Constraints

• 1 <= nums.length <= 10^5
• -10^5 <= nums[i] <= 10^5
• Median values should be exact (no floating-point rounding issues for the given test cases).