Problem Description

There are $n$ students in Xiao Lan's class. After an exam, Xiao Lan wants to analyze the students' scores. The score of the $i$-th student is $a_i$. After Xiao Lan has checked the scores of the first $x$ students, he can choose any $k$ students from $1 \sim x$ and compute the variance of these $k$ scores. What is the minimum number of students' scores Xiao Lan must check so that it is possible to choose $k$ students whose variance is less than a given value $T$?

Hint: The variance $\sigma^2$ of $k$ numbers $v_1, v_2, \cdots , v_k$ is defined as $\sigma^2=\dfrac {\sum_{i=1}^k(v_i-\bar v)^2} k$, where $\bar v$ is the average of $v_i$, $\bar v = \dfrac {\sum_{i=1}^k v_i} k$.

Input Format

The first line contains three positive integers $n, k, T$, separated by one space.

The second line contains $n$ positive integers $a_1, a_2, \cdots, a_n$, separated by one space.

Output Format

Output one line containing one integer, the answer. If the condition cannot be satisfied, output $-1$.

5 3 1
3 2 5 2 3

4

Hint

After checking the scores of the first three students, you can only choose $3, 2, 5$, and the variance is $1.56$.

After checking the scores of the first four students, you can choose $3, 2, 2$, and the variance is $0.22 < 1$, so the answer is $4$.

Constraints:

For $10\%$ of the testdata, $1 \le n, k \le 10^2$.

For $30\%$ of the testdata, $1 \le n, k \le 10^3$.

For all testdata, $1 \le n, k \le 10^5$, $1 \le T \le 2^{31} -1$, $1 \le a_i \le n$.

Translated by ChatGPT 5