题目描述

在一个古老的王国中，有一位聪明的国王。他的王国由许多村庄组成，每个村庄都有一个独特的资源值。为了使资源分布更加合理，他设计了一个计划，通过调整部分村庄的资源值，来实现资源的优化分配。

• 国王可以选择一个连续的村庄区间 [l, r]，并将这个区间内所有村庄的资源值统一调整为该区间中所有资源值的中位数。
• 为了节约资源调整的开销，国王最多只能进行 k 次这样的操作。

中位数是指该区间排序后第 ⌈(r-l+1)/2⌉ 小的数

经过操作后，国王希望使得村庄资源分布的最小值尽可能大，以便所有村庄的基本生活条件得到保障。

你的任务是帮助国王设计一个调整方案，使调整结束后，资源分布的最小值达到最大。

输入格式

第一行两个正整数n,k表示村庄总数和操作次数上限。

第二行n个非负整数$a_i$表示初始时每个村庄的资源数。

输出格式

输出k次操作以内，最小资源数的最大值

样例输入1

10 2
1 10 2 8 2 2 3 4 7 2

样例输出1

3

样例输入2

20 2
1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1

样例输出2

1

数据范围

所有数据： $1\le n\le 3\times 10^5$ ， $1\le a_i\le 10^9$ ， $1\leq k\leq n$ 。