URI Online Judge | 3107

Pulo do Sapo

Por Giovanna Kobus Conrado, University of São Paulo BR Brazil

Timelimit: 3

Um sapinho quer atravessar um rio. Infelizmente o rio talvez seja largo demais para o sapinho atravessá-lo com um pulo só. Felizmente, existem pedras localizadas convenientemente no meio do rio que o sapinho pode usar para ajudá-lo.

Diremos que a margem na qual o sapinho começa está localizada em 1 e que a outra margem está localizada em M. As N pedras estão localizadas em S1, ... , Sn. A princípio o sapo pode pular do lugar i ao j se há uma margem ou uma pedra em i e em j e i < j.

O sapo pode realizar dois tipos de pulo: um pulo curto e um pulo longo. Ele pode realizar um pulo curto entre i e j se ele pode realizar um pulo entre i e j e a distância entre i e j é menor ou igual a X e ele pode realizar um pulo longo entre i e j se ele pode realizar um pulo entre i e j e a distância entre i e j é menor ou igual a Y.

Se o sapo fizer dois pulos longos seguidos, suas pernas ficam doloridas e ele pode cair no rio. Ajude a determinar o menor número possível de pulos necessários para o sapo atravessar o rio.

Entrada

A primeira linha da entrada contém dois inteiros N (0≤N≤106) e M (2≤M≤109): o número de pedras e a localização a segunda margem do rio.

A segunda linha da entrada contém N inteiros: o i-ésimo desses é a localização da i-ésima pedra (1<Si<M). A localização das pedras será dada em ordem crescente e é garantido que todas as pedras estarão em lugares distintos.

A terceira linha da entrada contém dois inteiros X e Y (1≤X<Y≤109), os tamanhos do pulo curto e do pulo longo, respectivamente.

Saída

A saída deve conter um único inteiro: o número mínimo de pulos necessários para o sapo atravessar o rio sem realizar dois pulos longos ou -1 se o sapo não consegue atravessar o rio.

Exemplo de Entrada Exemplo de Saída

3 6
3 4 5
1 3

3