Chegou hoje a Atenas um grande carregamento de N colunas dóricas, dispostas numa linha ordenada, destinado a fazer um grande templo para honrar o grande deus Chronos. Infelizmente, mais uma vez a empresa de entregas enganou-se no pedido e agora os Atenienses ficaram com um conjunto de colunas inúteis. O problema é que cada coluna tem uma altura h, sendo que para construir o templo é preciso unir as várias colunas duas a duas (ver imagem em baixo para referência). Se a altura de um par de colunas diferir por mais de K, não é possível uni-las, pois a construção fica demasiado instável.
Para além da restrição de alturas, também a ordem das colunas não pode ser alterada da ordem original por causa dos encaixes! Desesperados, os Atenienses consultaram o grande Tales de Mileto e ele só vê uma solução: retirar um conjunto de colunas quaisquer, de maneira a que nas restantes não haja pares de colunas adjacentes que difiram de uma altura de mais de K, para que seja possível completar o templo.
O tempo é escasso e queremos obter um conjunto de colunas para construir o templo. Contudo, para não enfurecer ainda mais Chronos, o conjunto escolhido tem de conter o máximo número de colunas possível! Tens de ajudar os pobres atenienses...
Dado um conjunto de N inteiros positivos e um inteiro K, determinar o tamanho da maior subconjunto (uma subsequência não necessáriamente contígua) onde cada par de elementos seguidos não difere por mais de K unidades (ou seja, a diferença entre eles é inferior ou igual < K).
Na primeira linha vem um inteiro N e um inteiro K, indicando respectivamente o número de colunas e a máxima diferença de alturas entre duas colunas seguidas.
Segue-se uma linha com N inteiros hi representando a altura de cada coluna, por ordem.
Uma única linha com um inteiro representando o tamanho do subconjunto máximo nas condições dadas.
São garantidos os seguintes limites em todos os casos de teste:
| 1 ≤ N ≤ 105 | Número de colunas | |
| 1 ≤ K ≤ N | Distância adjacente máxima | |
| 1 ≤ hi ≤ 105 | Altura de uma coluna |
Para um conjunto de casos de teste valendo 20% dos pontos, acontece sempre que N≤20.
Para um conjunto de casos de teste valendo 45% dos pontos, acontece sempre que N≤4 000.
Para um outro conjunto de casos de teste valendo mais 30% dos pontos, acontece sempre que K≤20.
7 2 1 4 6 2 1 3 4
5
O subconjunto correspondente à resposta é o [1, 2, 1, 3, 4]. É fácil de ver que cada par de elementos está a uma distância de 2 ou menos (2 - 1 ≤ 2, 2 - 1 ≤ 2, 3 - 1 ≤ 2, 4 - 3 ≤ 2). Nota também que não é possível ter um subconjunto maior.
8 4 1 6 3 4 9 2 3 3
6