Minimum Check Count for Low Variance Subset

In a class of \(n\) students, each student has a score \(a_i\) after an exam. Xiaolan wants to verify his classmates' scores one by one. After checking the scores of the first \(x\) students, he is allowed to select any \(k\) scores among these \(x\) scores and compute their variance. The variance \(\sigma^2\) of \(k\) numbers \(v_1,v_2,\dots,v_k\) is defined as:

[ \sigma^2 = \frac{1}{k}\sum_{i=1}^{k}(v_i-\bar{v})^2 \quad\text{with}\quad \bar{v}=\frac{1}{k}\sum_{i=1}^{k}v_i, ]

Given a threshold value \(T\), determine the minimum number \(x\) (with \(x\ge k\)) such that among the first \(x\) scores it is possible to choose \(k\) scores whose variance is < \(T\). If no such \(x\) exists, output \(-1\).

Note: The \(k\) scores that achieve the minimum variance can be chosen in any order from the first \(x\) students.

inputFormat

The first line contains three numbers \(n\), \(k\) and \(T\) (where \(n\) is the total number of students, \(k\) is the number of scores to choose, and \(T\) is the variance threshold).

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the scores.

outputFormat

Output a single integer: the minimum \(x\) such that among the first \(x\) scores there exists a subset of \(k\) scores with variance strictly less than \(T\), or \(-1\) if no such \(x\) exists.

sample

5 2 1
1 2 3 2 1

2