Median Maintenance Data Structure

You are given a sequence of integers. Your task is to design a data structure that can add numbers and output the median of all added numbers efficiently. The median of a sequence is defined as follows: if the sequence (when sorted) has an odd number of elements, the median is the middle element; if it has an even number of elements, the median is the average of the two middle elements. In mathematical terms, if the sorted sequence is \(a_1 \le a_2 \le \cdots \le a_n\), then:

• If \(n\) is odd, \(\mathrm{median} = a_{(n+1)/2}\).
• If \(n\) is even, \(\mathrm{median} = \frac{a_{n/2}+a_{n/2+1}}{2}\).

Your implementation should use heaps (priority queues) to achieve efficient insertion and median finding.

inputFormat

The input is given from stdin and has the following format:

1. The first line contains an integer \(n\) denoting the number of elements.
2. The second line contains \(n\) space-separated integers, representing the numbers in the order they are added to the data structure.

outputFormat

Output the median value to stdout. If the median is an integer, print it without any decimal point. If it is a fraction, print the decimal value (for example, 1.5).

1
1

1