Problem Description

Given an integer sequence $a$ of length $n$, you may perform the following operation at most $k$ times:

• Choose an interval $[l, r]$ such that $1 \leq l \leq r \leq n$, and replace all numbers in $[l, r]$ with the median of this interval.

You want to make the minimum value of $a$ as large as possible after the operations.

Definition of the median here: for a sequence of length $len$, its median is defined as the $\left\lceil \frac{len}{2} \right\rceil$-th smallest number in the sequence.

Input Format

The first line contains two integers $n, k$.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$.

Output Format

Output one line containing the maximum possible value of the minimum element of the sequence after at most $k$ operations.

10 2
2 8 3 2 5 7 10 4 9 7

7

30 3
1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0

0

31 3
1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1

1

Hint

For $100\%$ of the testdata, $1 \leq n \leq 4 \times 10^5$, $0 \leq k \leq n$, and $0 \leq a_i \leq 10^9$.

Translated by ChatGPT 5