You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

老师在班级黑板上写了$n$个整数, 排成一行, 让同学们随机选一段区间, 然后研究这个区间的平均值, 中位数等等.

区间指的是这个序列的一段连续的区间, 不能为空, 但是可以只有一个数.

小龙选择了平均值这个性质来研究, 他发现, 区间的平均值, 有的大, 有的小.他准备给这些区间分类.

如果一个区间的平均值大于等于$m$, 则是好区间, 否则为坏区间. 但是小龙还没确定$m$的值.

小龙喜欢好区间, 不喜欢坏区间, 他希望好区间的个数不少于$k$个. 在此基础上, 小龙希望$m$的值尽量的大, 并且是一个整数.

现在小龙想知道, 他能找到的最大的整数$m$是多少. 如果找不到符合条件的$m$, 输出NO

保证给定的$k$大于零.

输入格式

第一行有两个整数$n, k$，代表序列的长度和好区间个数的下界. 接下来一行有$n$个整数, 代表每一个数的值, 分别为$a_1, a_2...a_i...a_n$.

输出格式

输出一行, 如果找不到符合条件的$m$, 输出NO

如果可以找到符合条件的$m$, 输出一个整数, 代表最大的$m$.

样例 #1

样例输入 #1

4 3
3 1 2 4

样例输出 #1

3

样例 #2

样例输入 #2

4 20
3 1 2 4

样例输出 #2

NO

样例 #3

样例输入 #3

4 10
3 -1 2 4

样例输出 #3

-1

样例 #4/#5/#6/#7

见下发文件中ex_average4/5/6/7.in/out

样例解释

对于样例$1$, 大于等于$3$的区间个数有$3$个, 大于等于$4$的区间个数为$1$个, 因此$m$最大为$3$

对于样例$2$, 找不到$20$个区间, 因此输出NO

对于样例$3$, 一共有$10$个区间, 最小的区间值为$-1$, 因此输出$-1$

数据范围

对于$20\%$的数据, $1 ≤ n ≤ 100$

对于$40 \%$的数据, $1 ≤ n ≤ 5000$

对于另外$20\%$的数据, $0 ≤ a_i ≤ 10$

对于$100\%$的数据, $1 ≤ n ≤ 10^5，0 < k ≤ 10^9, -10^9 ≤ a_i ≤ 10^9$

其他要求

每个测试点时限：$3$s 内存上限：$512$M