Maximize the Minimum Value

You are given an array a consisting of n integers and an integer k representing the maximum number of operations allowed. In each operation, you can choose an interval [l, r] (with 1 ≤ l ≤ r ≤ n) and replace every element in this interval by its median. Here, the median of a sequence of length len is defined as the \(\lceil\frac{len}{2}\rceil\)-th smallest number in that sequence.

Your task is to maximize the minimum value in the array after performing no more than k operations.

Note: The median is defined in \(\LaTeX\) as
\[ \text{median} = \text{the } \left\lceil\frac{len}{2}\right\rceil \text{-th smallest element} \]

inputFormat

The first line contains two integers n and k: the length of the array and the maximum number of operations.

The second line contains n integers a₁, a₂, ..., a_n separated by spaces.

outputFormat

Output a single integer representing the maximum possible minimum value of the array after performing at most k operations.

sample

5 1
1 2 3 4 5

3