Sau khi đọc đúng mật mã hài hòa, cánh cổng đá ngàn năm tuổi cuối cùng cũng ầm ầm mở tung ra hai bên, thế nhưng khung cảnh chào đón Ash bên trong lại không phải là những kho báu cổ xưa hay những bí kíp huấn luyện Pokemon huyền thoại như cậu vẫn hằng mong đợi, mà thay vào đó là một căn cứ ngầm đồ sộ được xây dựng hoàn toàn bằng kim loại lạnh lẽo. Thật không thể tin nổi, tổ chức tội phạm khét tiếng Team Rocket bằng một cách mờ ám nào đó đã đi trước cậu một bước, khoan phá lòng đất và thiết lập một đại trung tâm thao túng tín hiệu vô tuyến hòng kiểm soát tâm trí của toàn bộ các loài Pokemon hoang dã sinh sống xung quanh khu vực.

Đi dọc theo hành lang trung tâm dài hun hút của căn cứ, Ash kinh ngạc phát hiện ra chúng đã rải chính xác \(N\) trạm phát sóng gây nhiễu não bộ, được xếp thành một hàng ngang thẳng tắp, sừng sững như những con quái vật sắt thép. Các thông số trên màn hình điều khiển cho thấy, trạm thứ \(i\) đang không ngừng phát ra những luồng sóng nhiễu độc hại với mức công suất kinh hoàng là \(P_i\). Nhìn những Pokemon nhỏ bé bên ngoài đang dần mất đi ý thức và trở nên hung hãn, máu nóng trong người Ash sôi lên sùng sục; cậu phẫn nộ đến tột độ trước dã tâm thâm độc này và quyết tâm phải phá hủy toàn bộ mạng lưới tín hiệu bằng chiêu đòn tấn công hệ điện tối thượng và mạnh mẽ nhất của Pikachu.

Theo lý thuyết chiến đấu, một luồng sét cực đại khi phóng ra có khả năng lan truyền qua các vật dẫn và phá hủy một dãy các trạm phát sóng đứng liên tiếp nhau. Thế nhưng, thủ lĩnh tối cao Giovanni của Team Rocket là một kẻ vô cùng gian xảo và am hiểu khoa học công nghệ. Hắn đã lường trước được những cuộc tập kích và lắp đặt lên toàn bộ hệ thống một màng lọc phản xạ điện từ thông minh: Tia sét của Pikachu chỉ có thể truyền qua và phá hủy thành công một đoạn liên tiếp các trạm nếu và chỉ nếu tập hợp công suất của các trạm nằm trong đoạn bị tấn công đó tạo thành một dãy số mà phần tử trung vị của dãy phải đạt đến hoặc vượt qua một mức ngưỡng năng lượng tới hạn \(X\) nào đó để phá vỡ rào cản.

(Để hiểu rõ hơn về hệ thống phòng thủ này, trung vị của một dãy gồm \(L\) phần tử được định nghĩa một cách chặt chẽ là phần tử đứng ở vị trí thứ \(\lfloor \frac{L+1}{2} \rfloor\) khi người ta tiến hành sắp xếp toàn bộ dãy số đó theo thứ tự tăng dần từ nhỏ đến lớn. Ví dụ, nếu đoạn tấn công trúng vào \(3\) trạm có công suất là \([4, 1, 2]\), sau khi sắp xếp lại thành \([1, 2, 4]\) thì trung vị của đoạn này chính là \(2\)).

Do Pikachu đã phải vắt kiệt sức lực sau chuỗi hành trình băng rừng vượt bão dài ngày, Ash nhẩm tính trong đầu rằng cậu chỉ có thể ra lệnh cho Pikachu gồng mình tung đòn đánh vào một đoạn liên tiếp các trạm phát sóng có độ dài chính xác bằng \(L\), không hơn không kém. Để đòn đánh tạo ra uy lực xuyên phá kinh hoàng nhất làm lõi hệ thống phòng thủ của Giovanni phải quá tải và nổ tung, Ash vô cùng khao khát muốn chọn ra một đoạn mục tiêu có độ dài \(L\) sao cho giá trị trung vị của đoạn đó đạt ngưỡng lớn nhất có thể. Giữa lằn ranh sinh tử và áp lực thời gian đang đếm ngược, bạn hãy phát huy khả năng tư duy thuật toán để tìm ra giá trị trung vị tối đa đó, giúp Ash định vị chính xác mục tiêu cần triệt hạ.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(L\) (\(1 \le L \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(P_1, P_2, \dots, P_N\) (\(1 \le P_i \le 10^9\)) mô tả công suất trạm.

Output

• In ra một số nguyên duy nhất là giá trị trung vị lớn nhất có thể đạt được của một đoạn liên tiếp các trạm có độ dài đúng bằng \(L\).

Example

5 3
1 4 2 5 3

4

6 4
10 20 30 10 20 30

20

4 2
5 10 15 20

15

Scoring

• Subtask \(1\) (\(30\%\) điểm): \(N \le 100\).
• Subtask \(2\) (\(30\%\) điểm): \(N \le 2000\).
• Subtask \(3\) (\(40\%\) điểm): Không còn ràng buộc gì thêm.