Stream Processor: Median and Average Queries

You are given a stream of integers and a sequence of operations to perform. There are three types of operations:

1. Insert Operation: Insert an integer into the stream.
2. Median Query: Query the median of all inserted numbers. The median is defined as follows:

[ \text{median} = \begin{cases} a_{\frac{n+1}{2}}, & \text{if } n \text{ is odd}\ \frac{a_{\frac{n}{2}} + a_{\frac{n}{2}+1}}{2}, & \text{if } n \text{ is even} \end{cases} ]

where (a) is the sorted list of numbers.

3. Average Query: Query the average of all inserted numbers, computed as

[ \text{average} = \frac{\sum_{i=1}^{n} a_i}{n} ]

For an empty stream, both queries should output 0.0. The operations are given from standard input (stdin) and the result of each query (Median or Average) should be printed on a separate line to standard output (stdout).

inputFormat

The first line contains an integer (n) ((1 \le n \le 10^5)) which denotes the number of operations. Each of the next (n) lines contains an operation in one of the following formats:

• I x: Insert integer \(x\) into the stream.
• M: Output the median of the current stream.
• A: Output the average of the current stream.

It is guaranteed that all operations are valid. For queries on an empty stream, output 0.0.

outputFormat

For each query operation (i.e., operations 'M' and 'A'), output the result on a new line in floating-point format.## sample

5
I 1
I 3
I 2
M
A

2.0
2.0

</p>