Problem Statement

You are given a list ~x~ of ~n~ integers ~x = [x_1, x_2, ..., x_n]~.

You wish to determine the median for each prefix of ~x~. For example given ~[1, 2, 9, 7]~, you want to determine:

• The median of ~[1]~, then
• The median of ~[1, 2]~, then
• The median of ~[1, 2, 9]~, then
• The median of ~[1,2,9,7]~ ## Input Format

Your first line of input will contain a single integer ~n~. Your next line will contain ~n~ integers space-separated representing ~x~.

Output Format

You should output ~n~ space-separated integers representing the median of each prefix of ~x~.

Constraints

• ~1 \leq n \leq 10^5~
• ~-10^9 \leq x_i \leq 10^9~ ## Sample Cases

Input 1

10
1 2 9 7

Output 1

1 1.5 2 5.5

Explanation 1

There are 7 integers less than 14, being ~-2, 1, 2, 4, 5, 6, 10~. There are 4 integers less than 5, being ~-2, 1, 2, 4~. There are 6 integers less than 7, being ~-2, 1, 2, 4, 5, 6~.