23584번 - Dominating Subarray 스페셜 저지다국어

An array $x_1, \ldots, x_\ell$ is a subarray of an array $y_1, \ldots, y_m$ if there exists an integer $i$ from $1$ to $m-\ell+1$ such that the following equalities hold: $y_i = x_1$, $y_{i+1} = x_2$, $\ldots$, $y_{i+\ell-1} = x_{\ell}$.

A subarray $b_1, \ldots, b_k$ of $a$ is $k$-dominating if for any subarray $c_1, \ldots, c_k$ of $a$, the following inequalities hold: $b_1 \ge c_1$, $b_2 \ge c_2$, $\ldots$, $b_k \ge c_k$.

You are given an array $a_1, \ldots, a_n$. Find any occurrence of a $k$-dominating subarray of $a$ if it exists.

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 100\,000$), the length of the array $a$ and the parameter. The second line contains $n$ integers $a_1, \ldots, a_n$ ($1 \le a_i \le 10^6$), the elements of the array.

Print "-1" if there is no $k$-dominating subarray in $a$. Otherwise, print an integer $i$ from $1$ to $n-k+1$ such that $a_i, \ldots, a_{i+k-1}$ is a $k$-dominating subarray of $a$.