Mô tả và yêu cầu

Trung vị (Median.*)
Cho dãy số 𝑎1, 𝑎2, … ,𝑎𝑛. 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ụ 𝑎 =
{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ụ 𝑎 = {1,2,3,4} thì 𝑚𝑒𝑑𝑖𝑎𝑛 = 2+3 = 2.5
2
Yêu cầu: Cho 𝑛 số nguyên, với mỗi lần nhập 𝑎𝑖 bạn phải thực hiện:
- Thêm 𝑎𝑖 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:
- Dòng 1: số nguyên dương 𝑛 (1 ≤ 𝑛 ≤ 105)
- 𝑛 dòng tiếp theo, dòng thứ 𝑖 chứa số nguyên 𝑎𝑖 (0 ≤ 𝑎𝑖 ≤ 105)

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

Ví dụ

INPUT                       OUTPUT                                Giải thích

  6                          12.0                            {12}. Median = 12.0

  12                         8.0                             {4;12}. Median = 8.0

  4                          5.0                             {4;5;12}. Median = 5.0

  5                          4.5                             {3;4;5;12}. Median = 4.5

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

  8                          6.0

  7