Se te da un arreglo de longitud y un entero . Puedes eliminar cualquier número de elementos del arreglo (posiblemente cero). ¿Cuál es el número mínimo de elementos que se deben eliminar del arreglo, de modo que en el arreglo final no haya un subarreglo simple de longitud ?
Un arreglo de longitud se llama simple si sus elementos son estrictamente crecientes. Formalmente, b_i < b_{i+1} para todo 1 \le i < m.
Nota que k \ge 3.
Un subarreglo de un arreglo es un segmento contiguo de . Formalmente, un arreglo es un subarreglo de si existen índices y tales que 1 \le l \le r \le n y b = (a_l, a_{l+1}, \ldots, a_r).
Considera el arreglo a = (3, 1, 4, 1, 5, 9, 2). (3,1,4), (1,4,1,5) , son subarreglos de (desde el índice hasta , hasta y hasta respectivamente). (3,1,5) no es un subarreglo, ya que los elementos no son contiguos.
La primera línea contiene un entero (1 \le t \le 10^5) — el número de casos en un archivo de entrada.
Cada caso se describe en dos líneas. La primera línea contiene enteros (3 \le k \le n \le 2 \cdot 10^5).
La segunda línea contiene enteros a_1, a_2, \ldots, a_n (0 \le a_i \le 10^9).
Se garantiza que la suma de sobre todos los casos no excede 2 \cdot 10^5.
Para cada caso, imprime el número mínimo de elementos que se deben eliminar del arreglo, de modo que en el arreglo final no haya un subarreglo simple de longitud .
Ejemplo 1
En el primer caso de prueba, podemos eliminar el y el elementos del arreglo, resultando en [3,4,5]. No hay un subarreglo simple de longitud . Se puede demostrar que esta es la mejor solución posible.
En el segundo caso de prueba, podemos eliminar el y el elementos del arreglo, resultando en [1,3,3,5]. No hay un subarreglo simple de longitud . Se puede demostrar que esta es la mejor solución posible.
En el tercer caso de prueba, ya no hay un subarreglo simple de longitud .
( puntos): n=3;
( puntos): n=k;
( puntos): 0 \le a_i < k;
( puntos): a_i < 10;
( puntos): n \le 1000;
( puntos): sin restricciones adicionales;