当前没有测试数据。

问题描述

小蓝的班上有 $n$ 个人，一次考试之后小蓝想统计同学们的成绩，第 $i$ 名同学的成绩为 $a_i$​。当小蓝统计完前 $x$ 名同学的成绩后，他可以从 $1∼x$ 中选出任意 $k$ 名同学的成绩，计算出这 $k$ 个成绩的方差。小蓝至少要检查多少个人的成绩，才有可能选出 $k$ 名同学，他们的方差小于一个给定的值 $T$?

提示：$k$ 个数 $v_1,v_2,⋯ ,v_k$​ 的方差 $σ^2$ 定义为: $σ^2=\frac {\sum_{i=1}^k(v_i-\bar v)^2}k$​，其中 $\bar v$ 表示 $v$ 的平均值，$\bar v=\frac{\sum_{i=1}^kv_i}k$。

输入格式

输入的第一行包含三个正整数 $n,k,T$， 相邻整数之间使用一个空格分隔。

第二行包含 $n$ 个正整数 $a_1,a_2,⋯ ,a_n$,相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。如果不能满足条件, 输出 -1。

样例

5 3 1
3 2 5 2 3

4

样例说明

检查完前三名同学的成绩后,只能选出 $3,2,5$,方差为 $1.56$；

检查完前四名同学的成绩后,可以选出 $3,2,2$,方差为 $0.33<1$，所以答案为 $4$。

评测用例规模与约定

对于 $10\%$ 的评测用例，保证 $1≤n,k≤10^2$；

对于 $30\%$ 的评测用例，保证 $1≤n,k≤10^3$；

对于所有评测用例，保证 $1≤n,k≤10^5,1≤T≤2^{31}-1$。