Thành phố LA, nơi Jessie đang sinh sống và làm việc, đang có kế hoạch xây dựng một sân bay để phục vụ du lịch và giao thông trong thành phố.
Biểu đồ địa hình thành phố LA là một dãy số nguyên ~n~ phần tử ~h_1, h_2, h_3, \ldots, h_n~ — ~h_i~ thể hiện độ cao của địa hình thành phố ở vị trí thứ ~i~. Ban lãnh đạo dự án muốn tìm một khoảng địa hình phù hợp với chiều rộng là ~r~ để san phẳng và xây dựng sân bay. Như vậy ta có ~n-r+1~ khoảng địa hình khả quan.
Nhằm tối thiểu công sức san phẳng địa hình, ban lãnh đạo sẽ luôn chọn độ cao ~h_x~ là trung vị của các độ cao trong khoảng địa hình để làm chuẩn, nếu một vị trí có độ cao cao hơn chuẩn thì sẽ được đào đi, ngược lại nếu thấp hơn thì sẽ được lấp thêm đất. Nói cách khác, độ cao làm chuẩn để san phẳng sẽ là độ cao lớn thứ ~\lceil r/2 \rceil~ (chia làm tròn lên) trong khoảng địa hình đang xét.
Với vai trò là lập trình viên của dự án, ban lãnh đạo muốn bạn xác định độ cao san phẳng (độ cao làm chuẩn) lớn thứ ~k~ của ~n-r+1~ khoảng địa hình.
Input
Dòng đầu tiên chứa hai số nguyên ~n, r, k~ (~1 \leq r \leq n \leq 5 \cdot 10^5, 1 \leq k \leq n-r+1~);
Dòng thứ hai chứa ~n~ số nguyên ~h_1, h_2, \ldots, h_n~ (~|h_i| \leq 10^9~) — độ cao địa hình tại các vị trí của thành phố.
Output
In ra một số nguyên — độ cao san phẳng lớn thứ ~k~ để làm sân bay.
Scoring
- Subtask #1 (~40\%~): ~1 \leq n \leq 1\,000~
- Subtask #2 (~30\%~): ~1\,000 < n \leq 5 \cdot 10^5, k = 1~
- Subtask #3 (~30\%~): ~1\,000 < n \leq 5 \cdot 10^5, k > 1~
Sample Input 1
5 2 1
3 2 4 1 5
Sample Output 1
5
Sample Input 2
5 2 2
3 2 4 1 5
Sample Output 2
4
Bình luận