Incrementant segments#11790
Et donen un array de llargada i un enter . Pots eliminar qualsevol nombre d'elements de l'array (possiblement zero). Quin és el nombre mínim d'elements que s'han d'eliminar de l'array, de manera que l'array final no hi hagi cap subarray simple de llargada .
Un array de llargada s'anomena simple si els elements són estrictament creixents. Formalment, b_i < b_{i+1} per a tot 1 \le i < m.
Tingués en compte que k \ge 3.
Un subarray d'un array és un segment contigu de a. Formalment, un array és un subarray d' si existeixen alguns índexs i de manera que 1 \le l \le r \le n i b = (a_l, a_{l+1}, \ldots, a_r).
Considera l'array a = (3, 1, 4, 1, 5, 9, 2). (3,1,4), (1,4,1,5) , són subarrays d' (de l'índex al , del al i del al respectivament). (3,1,5) no és un subarray, ja que els elements no són contigus.
La primera línia conte un enter (1 \le t \le 10^5) — el número de casos en un fitxer d'entrada.
Cada cas està descrit per dues línies. La primera línia conté els enters (3 \le k \le n \le 2 \cdot 10^5).
La segona línia conté enters a_1, a_2, \ldots, a_n (0 \le a_i \le 10^9).
Es garanteix que la suma de en tots els casos no excedeix 2 \cdot 10^5.
Per cada cas imprimeix el mínim nombre d'elements que s'han d'eliminar de l'array, de manera que a l'array final nno hi hagi cap subarray simple de llargada .
Example 1
En el primer cas, podem eliminar el r i n elements de l'array, donant com a resultat [3,4,5]. No hi ha cap subarray simple de llargada . Es pot demostrar que aquesta és la millor solució possible.
En el segon cas, podem eliminar el n i t elements de l'array, donant com a resultat [1,3,3,5]. No hi ha cap subarray de llargada . Es pot demostrar que aquesta és la millor solució possible.
En el tercer cas, no hi ha cap subarray simple de llargada .
( punts): n=3;
( punts): n=k;
( punts): 0 \le a_i < k;
( punts): a_i < 10;
( punts): n \le 1000;
( punts): no hi ha condicions adicionals;