WhiteRaptor a enfin trouvé ses semblables dans TheRaptorLand ! Contrairement au WhiteRaptor ordinaire, TheRaptorLand possède un assortiment de raptors colorés : le PinkRaptor, le BlueRaptor et le GreenRaptor.
WhiteRaptor a aligné les $n$ raptors de TheRaptorLand, numérotés de $1$ à $n$ de gauche à droite. Le $i$-ème raptor en partant de la gauche a pour couleur $c[i]$. Il souhaite choisir certains raptors pour lui tenir compagnie dans son sous-sol pour toujours. Cependant, il ne peut le faire qu'en supprimant zéro ou plusieurs raptors aux extrémités gauche et droite de la ligne, et en conservant tous les raptors restants.
Pour s'assurer qu'aucun des raptors restants ne soit ostracisé, il veut que la différence entre la fréquence de la couleur de raptor la plus commune et la fréquence de la couleur de raptor la moins commune n'excède pas $k$. Notez que si aucun raptor d'une certaine couleur ne reste, la fréquence de la couleur de raptor la moins commune sera $0$.
Aidez WhiteRaptor à trouver le nombre maximum de raptors qu'il peut garder !
Entrée
Votre programme doit lire depuis l'entrée standard.
La première ligne de l'entrée contient deux entiers $n$ et $k$.
La deuxième ligne de l'entrée contient $n$ entiers séparés par des espaces $c[1], c[2], \dots, c[n]$.
Sortie
Votre programme doit écrire sur la sortie standard.
Affichez un entier, le nombre maximum de raptors qu'il peut garder.
Sous-tâches
Pour tous les cas de test, l'entrée satisfera les bornes suivantes :
- $1 \le n \le 200\,000$
- $0 \le k \le 200\,000$
- $1 \le c[i] \le 3$ pour tout $1 \le i \le n$
Votre programme sera testé sur des instances d'entrée qui satisfont les restrictions suivantes :
| Sous-tâche | Score | Contraintes supplémentaires |
|---|---|---|
| 0 | 0 | Cas de test d'exemple |
| 1 | 5 | $n \le 500$ |
| 2 | 9 | $n \le 2000$ |
| 3 | 11 | $c[i] \le 2$ |
| 4 | 15 | $k = 0$ |
| 5 | 16 | Il existe un $1 \le j \le n$ tel que $c[i] \neq 3$ pour tout $i \le j$, et $c[i] = 3$ pour tout $i > j$ |
| 6 | 20 | Dans toute séquence contiguë de 3 raptors ou plus, la couleur 3 est la moins commune. |
| 7 | 24 | Aucune contrainte supplémentaire |
Exemples
Entrée 1
11 2 2 2 1 2 1 3 2 1 2 1 1
Sortie 1
7
Remarque 1
Du raptor 3 au raptor 9, le nombre de raptors avec $c[i] = 1, 2$ et $3$ sont respectivement 3, 3 et 1. Puisque la différence entre les fréquences maximale et minimale n'excède pas $k = 2$, cet ensemble de raptors satisfait le critère de WhiteRaptor.
Un exemple d'ensemble invalide de raptors est du raptor 3 au raptor 10, car l'ajout d'un autre raptor avec $c[i] = 1$ porte la fréquence de la couleur la plus commune à 4. La différence résultante entre les fréquences maximale et minimale est de 3, ce qui excède $k = 2$.
On peut montrer que 7 est le plus grand nombre de raptors que WhiteRaptor peut garder tout en satisfaisant son critère.
Entrée 2
6 2 2 1 3 3 3 3
Sortie 2
5
Remarque 2
WhiteRaptor devrait choisir les raptors du raptor 1 au raptor 5.
Entrée 3
7 0 1 2 1 2 1 2 1
Sortie 3
0
Remarque 3
Puisqu'aucune séquence contiguë de raptors ne contiendra de raptor avec $c[i] = 3$, la fréquence de la couleur la moins commune sera toujours 0. Cela signifie que WhiteRaptor ne peut sélectionner aucune séquence non vide de raptors. Par conséquent, la sortie est 0.
Notez que ce cas de test satisfait la sous-tâche 5 car nous pouvons assigner $j = n$ (aucun raptor de couleur 3 n'apparaîtra).