Problema C - Aerobus

A Aerobus é uma empresa que produz pás para hélices de aviões através de uma linha de montagem. A sua produção consiste numa fase inicial na qual diversos ferreiros aquecem metal e criam um formato inicial da pá, que será posteriormente refinada até ter o formato correto e numa fase de distribuição, onde a varias pás são empacotadas para serem enviadas para um armazém e esperarem compradores.

Hoje está-se a produzir um lote de N pás e a fase inicial de produção acaba de terminar e as pás estão prontas a empacotar. Cada pá é indexada por um número distinto entre 1 e N e encontra-se numa posição numa linha comprida. A i-ésima pá encontra-se na posição X_i, que é um inteiro entre 1 e 1 000 000 000. Todas as pás encontram-se em posições distintas e sabe-se que as posições das pás estão ordenadas, isto é, a pá 1 tem posição menor que a pá 2, a pá 2 menor que a pá 3, etc, ou usando as variáveis definidas, X₁ < X₂ < ... < X_N.

Uma pá só pode ser empacotada se também forem empacotadas pelo menos K pás que estiverem próximas de si o suficiente na linha de montagem, nomeadamente a uma distância de D unidades ou menos. As restantes pás têm de passar por um processo distinto mais dispendioso.

Por exemplo, considerem que há N=6 pás nas posições 2, 3, 4, 6, 10, 11, e que cada pá precisa de K=1 pás à distância de D=1 para ser empacotada. A imagem seguinte mostra esta situação.

Neste exemplo, a pá 4 (a que se encontra na posição 6) não está a distância 1 ou menor de nenhuma outra pá, portanto não pode ser empacotada. Já as pás 1 (posição 2), 2 (posição 3) e 3 (posição 4) podem ser empacotadas as 3 em conjunto, pois a pá 1 está a uma distância de 1 unidade da pá 2, a pá 2 está a uma distância de 1 unidade da pá 1 e 3, e finalmente a pá 3 está a uma distância de 1 unidade da pá 2. Da mesma forma, as pás 5 (na posição 10) e 6 (na posição 11) podem ser empacotadas em conjunto pois estão a distância 1 uma da outra.

A Aerobus quer otimizar a linha de montagem, nomeadamente quer maximizar o número de pás a empacotar na fase de distribuição, mas seguindo a regra anterior. Para o exemplo dado, o máximo de pás a empacotar é 5, nomeadamente ao empacotarmos as pás 1, 2, 3, 5 e 6, como mostra a figura seguinte (a sublinhado).

Para mais informação sobre este processo, considerem o caso de exemplo 2 no fim da página.

Consegues escrever um programa que calcula o número máximo de pás a empacotar e as imprime? É garantido que o conjunto máximo de pás é único (não há dois conjuntos válidos distintos com número máximo de pás).

O Problema

Dada uma linha de montagem na qual estão a ser produzidas N pás que se encontram em posições X_i, identificar o conjunto máximo de pás podem ser empacotadas em conjunto, onde cada pá no conjunto máximo está a uma distância menor ou igual a D de pelo menos K outras pás no conjunto.

Input

Na primeira linha vêm três inteiros, N que representa o número de pás, D que representa a distância máxima a considerar e K que representa o número de pás mínimo a considerar.

Segue-se uma linha com N números distintos ordenados por ordem crescente e separados por um espaço onde o i-ésimo é X_i e representa a posição da i-ésima pá.

Nota: todos os valores de X_i são distintos e vêm por ordem crescente.

Output

O output deve primeiro conter um inteiro que representa o número máximo A de pás a ser empacotado.

Devem seguir-se A inteiros ordenados por ordem crescente na mesma linha e separados por um espaço, indicando os índices das pás que podem ser empacotados em conjunto.

Nota: se A=0 devem imprimir uma linha vazia depois da primeira linha, caso contrário o resultado desse caso de teste será "Presentation Error".

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Os casos de teste deste problema estão organizados em 5 grupos com restrições adicionais diferentes:

Input do Exemplo 1

6 1 1
2 3 4 6 10 11

Output do Exemplo 1

5
1 2 3 5 6

Explicação do Exemplo 1

Este exemplo corresponde ao mencionado no enunciado.

Input do Exemplo 2

6 2 2
1 3 4 8 9 10

Output do Exemplo 2

3
4 5 6

Explicação do Exemplo 2

A imagem seguinte representa a solução deste exemplo.

Reparem que apesar da pá 2 ter duas pás a distância menor ou igual a 2 (a pá 1 e 3), a pá 1 só tem uma pá a uma distância menor ou igual a 2 e o mesmo para a pá 3, logo nunca podem ser empacotadas.

Input do Exemplo 3

6 1 2
2 3 4 6 10 11

Output do Exemplo 3

0