On vous donne un tableau de longueur et un entier . Vous pouvez supprimer n'importe quel nombre d'éléments du tableau (possiblement zéro). Quel est le nombre minimal d'éléments à supprimer du tableau, de sorte qu'il n'y ait pas de sous-tableau simple de longueur dans le tableau final ?
Un tableau de longueur est appelé simple si ses éléments sont strictement croissants. Formellement, b_i < b_{i+1} pour tout 1 \le i < m.
Notez que k \ge 3.
Un sous-tableau d'un tableau est un segment contigu de . Formellement, un tableau est un sous-tableau de s'il existe des indices et tels que 1 \le l \le r \le n et b = (a_l, a_{l+1}, \ldots, a_r).
Considérez le tableau a = (3, 1, 4, 1, 5, 9, 2). (3,1,4), (1,4,1,5) , sont des sous-tableaux de (de l'indice à , à et à respectivement). (3,1,5) n'est pas un sous-tableau, car les éléments ne sont pas contigus.
La première ligne contient un entier (1 \le t \le 10^5) — le nombre de cas dans un fichier d'entrée.
Chaque cas est décrit en deux lignes. La première ligne contient les entiers (3 \le k \le n \le 2 \cdot 10^5).
La deuxième ligne contient entiers a_1, a_2, \ldots, a_n (0 \le a_i \le 10^9).
Il est garanti que la somme de sur tous les cas ne dépasse pas 2 \cdot 10^5.
Pour chaque cas, affichez le nombre minimal d'éléments à supprimer du tableau, de sorte qu'il n'y ait pas de sous-tableau simple de longueur dans le tableau final.
Exemple 1
Dans le premier cas de test, nous pouvons supprimer les et éléments du tableau, ce qui donne [3,4,5]. Il n'y a pas de sous-tableau simple de longueur . Il peut être prouvé que c'est la meilleure solution possible.
Dans le deuxième cas de test, nous pouvons supprimer les et éléments du tableau, ce qui donne [1,3,3,5]. Il n'y a pas de sous-tableau simple de longueur . Il peut être prouvé que c'est la meilleure solution possible.
Dans le troisième cas de test, il n'y a déjà pas de sous-tableau simple de longueur .
( points): n=3;
( points): n=k;
( points): 0 \le a_i < k;
( points): a_i < 10;
( points): n \le 1000;
( points): pas de contraintes supplémentaires;