У вас есть массив \(a\) длины \(n\). Найдите такой подмассив \(a[l..r]\) длиной хотя бы \(k\), что у него максимально возможная медиана.
Медианой в массиве длины \(n\) называется элемент, стоящий на позиции \(\lfloor \frac{n + 1}{2} \rfloor\) после сортировки всех элементов в неубывающем порядке. Например: \(median([1, 2, 3, 4]) = 2\), \(median([3, 2, 1]) = 2\), \(median([2, 1, 2, 1]) = 1\).
Подмассив \(a[l..r]\) — это последовательная часть массива \(a\), то есть массив \(a_l,a_{l+1},\ldots,a_r\) для каких-то \(1 \leq l \leq r \leq n\), он имеет длину \(r - l + 1\).
Примечание
В первом примере все возможные массивы: \([1..3]\), \([1..4]\), \([1..5]\), \([2..4]\), \([2..5]\) и \([3..5]\), и во всех них медиана равна \(2\), соответственно, максимальная медиана также равна \(2\).
Во втором примере \(median([3..4]) = 3\).