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:

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í \(\left\lfloor \dfrac{n+1}{2} \right\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.

Input

• 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\)).

Output

• Kết quả của bài toán.

Input

%
4 2
1 3 2 4

Output

%
3

Input

%
4 1
1 2 2 4

Output

%
4

Input

%
11 2
3 2 3 2 11 5 2 3 9 10 11

Output

%
10

Input

%
11 6
3 2 3 2 11 5 2 3 9 10 11

Output

%
9

Notes

Trong ví dụ đầu tiên:

• Với dãy con độ dài \(2\): \((1, 3)\) có trung vị là \(1\), \((3, 2)\) có trung vị là \(2\), \((2, 4)\) có trung vị là \(2\);
• Với dãy con độ dài \(3\): \((1, 3, 2)\) có trung vị là \(2\), \((3, 2, 4)\) có trung vị là \(3\);
• Với dãy con độ dài \(4\): \((1, 3, 2, 4)\) có trung vị là \(2\).

Do đó trung vị lớn nhất đạt được là \(3\).

Scoring

• (20%) \(k = 2\), \(n = 3\);
• (20%) \(k = 1\);
• (30%) \(n \le 100\);
• (30%) Không có ràng buộc thêm.