Median

Cho dãy số \(a_1, a_2, \ldots, a_n\). Ta có định nghĩa median của một dãy số như sau:

• Nếu độ dài dãy là lẻ thì median = phần tử giữa của dãy sau khi sắp xếp. Ví dụ \(a = \{1, 2, 3\}\) thì median = 2.
• Nếu độ dài dãy là chẵn thì median = trung bình cộng của hai phần tử giữa của dãy sau khi sắp xếp. Ví dụ \(a = \{1, 2, 3, 4\}\) thì median = 2.5.

Yêu cầu: Cho \(n\) số nguyên, với mỗi lần nhập \(a_i\), bạn phải thực hiện:

• Thêm \(a_i\) vào dãy số.
• Tính median cho dãy số mới cập nhật.
• In ra median của các dãy số mới cập nhật trên từng dòng, mỗi median in ra theo định dạng 1 chữ số thập phân sau dấu phẩy.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \leq n \leq 10^5)\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(a_i\) \((0 \leq a_i \leq 10^5)\).

Output

• Ghi ra \(n\) số thực trên \(n\) dòng theo thứ tự là median của các dãy số.

Example

6
12
4
5
3
8
7

12.0
8.0
5.0
4.5
5.0
6.0

Scoring

• \(20\%\) số test có \(n \leq 100\).
• \(30\%\) số test có \(n \leq 1000\).
• \(20\%\) số test có dãy \(a\) là \(1\) dãy tăng dần.
• \(30\%\) còn lại không có ràng buộc gì thêm.