Trung vị

Dãy $A$ gồm $n$ số nguyên $a_1,a_2,\dots ,a_n$ được gọi là dãy không giảm nếu thỏa mãn: $a_1\le a_2\le \dots \le a_n$.

Trung vị của dãy các số nguyên $a_1,a_2,\dots ,a_n$ là phần tử xuất hiện ở vị trí $\lfloor \frac{n+1}{2}\rfloor$ sau khi dãy đó được sắp xếp lại thành dãy không giảm.

Ví dụ: Cho dãy $A=(2,3,4,2,8)$ sau khi sắp xếp lại thành dãy không giảm ta được dãy $(2,2,3,4,8)$, trung vị của dãy là phần tử $3$; dãy $B=(3,5,7,6)$ sau khi sắp xếp lại thành dãy không giảm ta được dãy $(3,5,6,7)$, trung vị của dãy là phần tử $5$. Trung vị của dãy chỉ có một phần tử là chính phần tử đó.

Yêu cầu: Cho dãy $A$ gồm $n$ số nguyên $a_1,a_2,\dots ,a_n$ và số nguyên $k$. Hãy xác định trung vị lớn nhất của mọi dãy con gồm ít nhất $k$ phần tử liên tiếp trong dãy đã cho.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n,k$ ($1\le k\le n\le {10}^5$);
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ ($1\le a_i\le n$; $i=1,2,\dots ,n$).

Dữ liệu ra

In ra kết quả bài toán.

Ràng buộc

• $1\le k\le n\le {10}^5$.
• $1\le a_i\le n$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $k=2$, $n=3$.
• Subtask 2 ($20\%$ số điểm): $k=1$.
• Subtask 3 ($30\%$ số điểm): $n\le 100$.
• Subtask 4 ($30\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ