题目描述

你需要维护一个初始为空的整数集合，支持以下操作：

1. 插入：向集合中加入一个整数。
2. 查询：查询当前集合的中位数。

每次插入操作后，你需要立即输出当前集合的中位数。

注意：如果当前集合大小为偶数，则中位数定义为排序后中间两个数的平均值；如果为奇数，则中位数定义为排序后中间的数。

输入格式

第一行包含一个整数 $n(1 \le n \le 10^5)$，表示操作次数。

接下来 $n$ 行，每行包含一个整数 $x(-10^9 \le x \le 10^9)$，表示要插入到集合中的数字。

注意：这里每次输入都是插入操作，插入后需要立即输出中位数。

输出格式

输出 $n$ 行，每行一个浮点数，表示每次插入操作后当前集合的中位数，结果保留一位小数。

样例输入 #1

6
1
3
5
2
4
6

样例输出 #1

1.0
2.0
3.0
2.5
3.0
3.5

样例解释 #1

• 插入 1 后：集合为 [1]，中位数为 1.0
• 插入 3 后：集合为 [1, 3]，中位数为 (1+3)/2 = 2.0
• 插入 5 后：集合为 [1, 3, 5]，中位数为 3.0
• 插入 2 后：集合为 [1, 2, 3, 5]，中位数为 (2+3)/2 = 2.5
• 插入 4 后：集合为 [1, 2, 3, 4, 5]，中位数为 3.0
• 插入 6 后：集合为 [1, 2, 3, 4, 5, 6]，中位数为 (3+4)/2 = 3.5

样例输入 #2

5
-1
-2
-3
-4
-5

样例输出 #2

-1.0
-1.5
-2.0
-2.5
-3.0

数据范围

• 对于 30% 的数据：$1 \le n \le 1000$
• 对于 60% 的数据：$1 \le n \le 50000$
• 对于 100% 的数据：$1 \le n \le 10^5，-10^9 \le x \le 10^9$