Problema C - Travessia Radical

O Clube Onimalaias é um clube profissional de escalada, um desporto muito exigente no que toca à capacidade física dos seus praticantes. A versão favorita dos inúmeros membros do clube é a escalada horizontal, em que o objetivo é atravessar, da esquerda para a direita, uma enorme parede. De modo a ser possível realizar a travessia, a parede possui N pontos de apoio, igualmente espaçados no que toca à componente horizontal, mas com diversas alturas. Podemos facilmente representar uma parede deste tipo pela sequência H das alturas dos seus pontos de apoio, da esquerda para a direita.

Ao praticar escalada horizontal, um atleta realiza várias transições, nas quais muda de estar apoiado no ponto i, a H_i unidades de altura, para estar apoiado no ponto j, a H_i unidades de altura. Mesmo para o mais aventurado praticante, o seu corpo tem tamanho finito, o que nos leva a considerar, para cada pessoa, o número L: a maior distância horizontal que uma pessoa consegue percorrer numa só transição. Com estas noções tidas em conta, podemos começar a pensar em estudar quão difícil é fazer escalada horizontal numa dada parede.

Pode não parecer, mas fazer sequer uma transição é muito exigente dum ponto de vista físico e é preciso muito treino até se conseguir realizar uma. Um conceito a ter em conta é a dificuldade de uma transição, que corresponde precisamente ao declive, em valor absoluto, da reta entre os pontos de apoio:

Parte I

Dada uma parede, queremos saber qual a transição mais difícil que se pode realizar. Isto é, dados o comprimento N da parede, a sequência das alturas H e o comprimento máximo de transição L, pretendemos encontrar o maior declive D_{i, j} tal que |i - j| ≤ L.

Visto que a resposta pode ser um número fracionário, a resposta estará correta se o erro absoluto e relativo for no máximo 0.01 (podem consultar os exemplos para mais informação).

Exemplo

Vamos supor que N = 5 e temos a seguinte sequência de alturas H = [1, 6, 2, 3, 5]. Alguns exemplos de declives:

Para este caso o maior declive é D_{1, 2}, por isso a resposta será 5 para qualquer L.

Respostas como 5.01 ou 4.99 têm um erro absoluto de no máximo 0.01 (e um erro relativo ainda menor), por isso também estão corretas.

Restrições:

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

Os casos de teste desta parte do problema estão organizados em 2 grupos com restrições adicionais diferentes:

Parte II

No entanto, também estamos interessados em saber quão experiente um praticante tem de ser para conseguir atravessar a parede desde o ponto de apoio 1 até ao ponto de apoio N.

Formalmente, queremos encontrar o menor número F para o qual existe uma sequência de transições que percorram toda a parede e onde nenhuma tem dificuldade superior a F, ou seja, para o qual existe uma sequência 1 = p₁ < p₂ < ... < p_k = N tal que para todo o i entre 1 e k - 1, p_{i + 1} - p_i ≤ L e que D_{pi, pi + 1} ≤ F.

Visto que a resposta pode ser um número fracionário, a resposta estará correta se o erro absoluto e relativo for no máximo 0.01 (podem consultar os exemplos para mais informação).

Exemplo

Vamos supor novamente que N = 5 e que temos a seguinte sequência de alturas H = [1, 6, 2, 3, 5]. Considerem L = 2.

Se fizermos a travessia do ponto 1 para o ponto 3 (cujo declive é de 0.5) e de seguida do ponto 3 para o ponto 5 (cujo declive é 1.5), o declive máximo que usámos é 1.5, logo a resposta é 1.5.

Respostas como 1.51 ou 1.49 têm um erro absoluto de no máximo 0.01 (e um erro relativo ainda menor), por isso também estão corretas.

Restrições:

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

Os casos de teste desta parte do problema estão organizados em 2 grupos com restrições adicionais diferentes:

Sumário de subtarefas

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

Input

A primeira linha contém um inteiro P, que representa a parte que o caso de teste representa. Se for 1, então o caso de teste refere-se à Parte I, se for 2 então refere-se à Parte II.

Segue-se uma linha com dois inteiros separados por espaços, N, representando o tamanho da sequência, e L, representando a distância máxima.

Segue-se uma linha com N inteiros separados por espaços, representando a sequência de alturas H.

Output

O Output deve conter apenas uma linha com um número. O número não precisa de ser arredondado e pode ter quantas casas decimais quanto necessárias, desde que o erro absoluto e relativo em relação à resposta seja no máximo 0.01.

Input do Exemplo 1

1
5 2
1 6 2 3 5

Output do Exemplo 1

5.000000000

Explicação do Exemplo 1

Este exemplo corresponde ao exemplo da Parte I mencionado no enunciado.

Input do Exemplo 2

2
5 2
1 6 2 3 5

Output do Exemplo 2

1.500000000

Explicação do Exemplo 2

Este exemplo corresponde ao exemplo da Parte II mencionado no enunciado.