Bạn nhận được một luồng dữ liệu gồm các số nguyên được truyền đến liên tục. Sau khi nhận được mỗi số mới, bạn hãy tính và in ra số trung vị (Median) của tất cả các số đã nhận được tính đến thời điểm hiện tại.

Nhắc lại về Số trung vị:

• Nếu số lượng phần tử của tập hợp là số lẻ, trung vị là phần tử đứng chính giữa khi tập hợp được sắp xếp tăng dần.
• Nếu số lượng phần tử là số chẵn, trung vị là trung bình cộng của 2 phần tử đứng chính giữa.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \le N \le 10^5~) là tổng số lượng các số sẽ được truyền đến.
• ~N~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~X~ (~-10^9 \le X \le 10^9~).

Kết quả

In ra ~N~ dòng, dòng thứ ~i~ là số trung vị của tập hợp sau khi nhận được ~i~ số đầu tiên. Kết quả in ra dưới dạng số thập phân với đúng 1 chữ số sau dấu phẩy.

Ví dụ

Input

4
5
15
1
3

Output

5.0
10.0
5.0
4.0

Giải thích

• Nhận 5: Tập hợp [5]. Trung vị = ~5.0~
• Nhận 15: Tập hợp [5, 15]. Trung vị = ~(5 + 15) / 2 = 10.0~
• Nhận 1: Tập hợp [1, 5, 15]. Trung vị = ~5.0~
• Nhận 3: Tập hợp [1, 3, 5, 15]. Trung vị = ~(3 + 5) / 2 = 4.0~