Busy Beaver est trop paresseux pour écrire une histoire intéressante pour ce problème, il vous a donc simplement donné un énoncé formel.
Définissons une $M$-séquence comme une séquence d'entiers positifs, chacun compris entre $1$ et $M$ inclus.
Une $M$-séquence est dite $K$-bonne si la différence absolue entre toute paire d'éléments adjacents est au plus $K$. Par exemple, $[1, 2, 3, 5, 5, 3, 2, 1]$ est $2$-bonne et $2024$-bonne, mais pas $1$-bonne. Nous considérons également les $M$-séquences de longueur $0$ ou $1$ comme étant $K$-bonnes.
Étant donné des entiers positifs $N$, $M$, $K$, $L$, et une $M$-séquence $a_1, \dots, a_N$ de longueur $N$, trouvez le nombre maximum possible d'éléments dans une $M$-séquence $b$, telle que :
- $b$ a $a$ comme préfixe ; et
- Chaque sous-séquence $K$-bonne de $b$ possède au plus $L$ éléments.
Rappelons qu'une sous-séquence d'une séquence est obtenue en supprimant certains éléments (éventuellement tous ou aucun) d'une séquence, sans réordonner les éléments restants.
Entrée
Il y a plusieurs cas de test. La première ligne contient un entier positif $T$ ($1 \le T \le 2 \cdot 10^5$), le nombre de cas de test.
La première ligne de chaque cas de test contient quatre entiers $N$, $M$, $K$, $L$ ($0 \le N \le 2 \cdot 10^5$, $1 \le M \le 10^9$, $0 \le K \le 10^9$, $1 \le L \le 10^9$).
La deuxième ligne d'un cas de test contient $a_1, \dots, a_N$ ($1 \le a_i \le M$). Si $N = 0$, alors cette ligne est ignorée.
Il est garanti que chaque sous-séquence $K$-bonne de $a$ possède au plus $L$ éléments. De plus, la somme de $N$ sur tous les cas de test ne dépasse pas $4 \cdot 10^5$.
Sortie
Pour chaque cas de test, affichez une ligne contenant le nombre maximum d'éléments dans $b$. Il peut être démontré que sous les contraintes du problème, le maximum existe toujours et ne dépasse pas $9 \cdot 10^{18}$.
Sous-tâches
- ($5$ points) $M \le K + 1$.
- ($5$ points) $K = 0$.
- ($10$ points) $N = 0$.
- ($15$ points) $N = 1$.
- ($30$ points) La somme de chacun des $N$, $M$, $K$ et $L$ sur tous les cas de test ne dépasse pas $3000$.
- ($35$ points) Aucune contrainte supplémentaire.
Exemples
Entrée 1
3 3 3 1 3 1 3 2 0 5 2 3 7 7 2 3 1 4 2 7 7 1 6
Sortie 1
5 6 7
Remarque
Dans le premier cas de test, une $M$-séquence $b$ possible est $[1, 3, 2, 3, 1]$, dont les sous-séquences $1$-bonnes, telles que $[3, 2, 3]$ et $[3, 2, 1]$, ont toutes une longueur au plus égale à $L = 3$.
Dans le deuxième cas de test, une $M$-séquence $b$ possible est $[1, 1, 5, 4, 2, 5]$, dont les sous-séquences $2$-bonnes, telles que $[5, 4, 2]$ et $[1, 1, 2]$, ont toutes une longueur au plus égale à $L = 3$.
Dans le troisième cas de test, il peut être démontré que la seule $b$ possible est $b = a$.