Cho dãy số a1,a2,…,an. 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 sort. 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+32=2.5

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

Thêm ai 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.

Dữ liệu: Vào từ file văn bản MEDIAN.INP

Dòng 1: số nguyên dương n (1≤n≤10^5)

n dòng tiếp theo, dòng thứ i chứa số nguyên ai (0≤ai10^5)

Kết quả: Ghi ra file văn bản MEDIAN.OUT n số nguyên trên n dòng theo thứ tự là median của các dãy số.

Ví dụ: MEDIAN.INP

6
12
4
5
3
8
7

MEDIAN.OUT

12.0
8.0
5.0
4.5
5.0
6.0

Giải thích

• {12}. Median = 12.0
• {4;12}. Median = 8.0
• {4;5;12}. Median = 5.0
• {3;4;5;12}. Median = 4.5

• {3;4;5;7;8;12}. Median = 6.0

  Tài liệu tham khảo