Segments croissants#11790

Segments croissants

1 seconde
256 mégaoctets
Moyen

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.

Entrée

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.

Sortie

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.

Exemples

Exemple 1

Loading
Loading

Note

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 .

Notation

  1. ( points): n=3;

  2. ( points): n=k;

  3. ( points): 0 \le a_i < k;

  4. ( points): a_i < 10;

  5. ( points): n \le 1000;

  6. ( points): pas de contraintes supplémentaires;