Даны два положительных целых числа \(n\) и \(k\), а также массив \(a\) из \(n\) целых чисел.
При выполнении операции вы можете выбрать любой подмассив размера \(k\) из \(a\), а затем удалить его из массива, не меняя порядок других элементов. Более формально, пусть \((l, r)\) — это операция над подпорядком \(a_l, a_{l+1}, \ldots, a_r\), такая что \(r-l+1=k\), тогда выполнение этой операции означает замену \(a\) на \([a_1, \ldots, a_{l-1}, a_{r+1}, \ldots, a_n]\).
Например, если \(a=[1,2,3,4,5]\) и мы выполним операцию \((3,5)\) над этим массивом, он станет \(a=[1,2]\). Помимо того, операция \((2, 4)\) приведет к \(a=[1,5]\), а операция \((1,3)\) приведет к \(a=[4,5]\).
Вам нужно повторять операцию, пока длина \(a\) больше \(k\) (что означает \(|a| \gt k\)). Какова наибольшая возможная медиана\(^\dagger\) всех оставшихся элементов массива \(a\) после процесса?
\(^\dagger\)Медиана массива длины \(n\) — это элемент, индекс которого равен \(\left \lfloor (n+1)/2 \right \rfloor\) после сортировки элементов в неубывающем порядке. Например: \(median([2,1,5,4,3]) = 3\), \(median([5]) = 5\), и \(median([6,8,2,4]) = 4\).
Примечание
В первом наборе входных данных подмассив \((l, r)\) может быть либо \((1, 3)\), либо \((2, 4)\). Таким образом, два получаемых конечных массива — это \([3]\) и \([2]\). Первый имеет большую медиану (\(3 > 2\)), поэтому ответ — \(3\).
Во втором наборе входных данных три получаемых конечных массива — это \([6, 4]\), \([3, 4]\) и \([3, 2]\). Их медианы равны \(4\), \(3\) и \(2\) соответственно. Ответ — \(4\).
В третьем наборе входных данных в конечном массиве остается только один элемент, и это может быть любой элемент начального массива. Наибольший из них — \(9\), поэтому ответ — \(9\).