Tính thời gian chờ trung vị của các cuốc xe công nghệ trong ca trực

Một ứng dụng gọi xe công nghệ ghi lại thời gian chờ (đơn vị: phút) của khách hàng cho từng cuốc xe trong một ca trực. Thay vì tính trung bình cộng (dễ bị lệch bởi vài cuốc xe chờ quá lâu), công ty muốn tính thời gian chờ trung vị (median) — giá trị nằm chính giữa dãy dữ liệu sau khi đã sắp xếp tăng dần.

Quy tắc tính trung vị của dãy đã sắp xếp gồm n phần tử:

• Nếu n là số lẻ, trung vị là phần tử ở đúng vị trí chính giữa của dãy đã sắp xếp.
• Nếu n là số chẵn, trung vị là trung bình cộng của hai phần tử ở giữa dãy đã sắp xếp.

Em hãy viết chương trình: đọc số lượng cuốc xe và dãy thời gian chờ, tự chọn và cài đặt một trong ba thuật toán sắp xếp đã học (chèn, chọn, hoặc nổi bọt) để sắp xếp dãy tăng dần, sau đó tính và in ra thời gian chờ trung vị.

Định dạng input: dòng đầu là số nguyên n (số cuốc xe); dòng thứ hai gồm n số nguyên cách nhau bởi dấu cách (thời gian chờ, phút).

Định dạng output: dòng đầu in dãy đã sắp xếp tăng dần (cách nhau bởi dấu cách); dòng thứ hai in theo định dạng Trung vi: X với X là giá trị trung vị tính được.