Problem Description

Given an integer sequence \(a\) of length \(n\), you can perform the following operation at most \(k\) times:

• Select an interval \([l, r]\) where \(1 \leq l \leq r \leq n\), and replace all numbers in \([l, r]\) with the median of this interval.

Your goal is to maximize the minimum value of \(a\) after performing these operations.

Regarding the definition of the median here: For a sequence of length \(len\), the median is defined as the \(\lceil \frac{len}{2} \rceil\)-th smallest number in the sequence.

Input Format

The first line contains two integers \(n\) and \(k\).

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

Output Format

A single line representing the maximum possible minimum value of the sequence after performing at most \(k\) operations.

Sample Input and Output

Sample Input #1

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

Sample Output #1

7

Sample Input #2

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

Sample Output #2

0

Sample Input #3

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

Sample Output #3

1

Notes

For \(100\%\) of the data, \(1 \leq n \leq 4 \times 10^5\), \(0 \leq k \leq n\), \(0 \leq a_i \leq 10^9\).

见题面 Input 部分

见题面 Output 部分