T565118 「2025 YAC Round 3」方差

在旧镇的学城，学士们要分析学城学徒的成绩数据，研究成绩的方差。学城有 $n$ 个学徒，第 $i$ 个学徒的成绩为 $a_i$。学士们在统计完**前 $x$ 个**学徒的成绩后，可以从 $1 \sim x$ 中选出任意 $k$ 个学徒，计算他们成绩的方差。现在，学士们想知道，他们**至少**需要检查多少个学徒的成绩，才能保证能选出 $k$ 个学徒，使得他们的成绩方差小于一个给定的值 $T$。 方差的公式为：对于选择的 $k$ 个成绩 $v_1, v_2, \dots, v_k$，它们的方差定义为： $$ \sigma^2 = \dfrac{\sum_{i=1}^k (v_i - \bar{v})^2}{k} $$ 其中，$\bar{v}$ 是这 $k$ 个成绩的平均值： $$ \bar{v} = \dfrac{\sum_{i=1}^k v_i}{k} $$

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

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

检查完前三名学徒的成绩后，只能选出 $3, 2, 5 $，方差为 $1.56 $； 检查完前四名学徒的成绩后，可以选出 $3, 2, 2 $，方差为 $0.22 < 1 $，所以答案为 $4 $。 对于所有评测用例，保证 $1 ≤ k ≤ n ≤ 10^5 $，$1 ≤ T ≤ 2 ^{31} -1 $，$1 ≤ a_i ≤ n $。