Trạm Cứu Hỏa Trung Vị Quận 7

Mô tả

Khu dân cư ven kênh Quận 7 đang có kế hoạch xây một Trạm Cứu hỏa mới. Dọc con đường chính phẳng nằm dọc kênh có $N$ căn nhà dân của các hộ gia đình. Ban quản lý muốn đặt Trạm Cứu hỏa đúng tại nhà của một người dân sao cho tổng khoảng cách di chuyển từ Trạm đến tất cả các nhà còn lại là nhỏ nhất có thể.

Quãng đường ở đây rất thẳng, mỗi căn nhà nằm ở một tọa độ số nguyên trên trục số. Nhiệm vụ của bạn là tìm tọa độ nhà dân nên chọn làm nơi đặt Trạm Cứu hỏa. Nếu có nhiều nhà đều thỏa mãn (tức là tổng khoảng cách bằng nhau và đều nhỏ nhất), hãy chọn tọa độ nhỏ nhất trong số đó.

Đầu vào

• Một mảng số nguyên houses đại diện cho tọa độ của các căn nhà.

Đầu ra

• Trả về một số nguyên là tọa độ nhà dân được chọn để đặt Trạm Cứu hỏa.

Ràng buộc

• $1 \le N \le 10^5$