Um canal de televisão de entretenimento transmite o programa «Колесо Фортуны». Durante o jogo, os participantes giram uma grande roda dividida em setores. Em cada setor dessa roda está escrito um número. Depois que a roda para, uma seta especial aponta para um dos setores. O número nesse setor determina o prêmio do jogador.
Um jovem participante percebeu que a roda desacelera durante a rotação porque a seta esbarra nas saliências da roda localizadas entre os setores. Se a roda gira com velocidade angular de $v$ graus por segundo e a seta, ao passar do setor $X$ para o setor seguinte, esbarra na próxima saliência, a velocidade angular atual da roda diminui em $k$ graus por segundo. Se $v \le k$, a roda não consegue superar o obstáculo e para. Nesse caso, a seta apontará para o setor $X$.
O jovem participante pretende girar a roda. Conhecendo a ordem dos setores, ele quer fazer a roda girar com uma velocidade inicial tal que, depois de parar, a seta aponte para o maior número possível. A roda pode ser girada em qualquer direção e receber uma velocidade angular inicial de $a$ a $b$ graus por segundo.
Escreva um programa que, dados a disposição dos números nos setores, as velocidades angulares iniciais mínima e máxima de rotação da roda e a redução da velocidade ao atravessar uma fronteira entre setores, calcule o prêmio máximo.
Entrada
A primeira linha do arquivo de entrada contém um inteiro $n$ — o número de setores da roda ($3 \le n \le 100$).
A segunda linha do arquivo de entrada contém $n$ inteiros positivos, cada um não superior a $1000$ — os números escritos nos setores da roda. Os números são dados na ordem dos setores no sentido horário. Inicialmente, a seta aponta para o primeiro número.
A terceira linha contém três inteiros: $a$, $b$ e $k$ ($1 \le a \le b \le 10^9$, $1 \le k \le 10^9$).
Saída
O arquivo de saída deve conter um único inteiro — o prêmio máximo.
Exemplos
Entrada 1
5 1 2 3 4 5 3 5 2
Saída 1
5
Entrada 2
5 1 2 3 4 5 15 15 2
Saída 2
4
Entrada 3
5 5 4 3 2 1 2 5 2
Saída 3
5
Nota
No primeiro exemplo, há as seguintes possibilidades: pode-se dar à roda uma velocidade inicial igual a $3$ ou $4$, fazendo a seta atravessar uma fronteira entre setores, ou uma velocidade inicial igual a $5$, permitindo que a seta atravesse 2 fronteiras entre setores. Na primeira possibilidade, girando a roda em uma direção, o prêmio será $2$; girando-a na direção oposta, será $5$. Na segunda possibilidade, girando a roda em uma direção, o prêmio será $3$; girando-a na outra, será $4$.
No segundo exemplo, só é possível uma velocidade inicial de rotação da roda: $15$ graus por segundo. Nesse caso, durante a rotação, a seta atravessará sete fronteiras entre setores. Assim, girando a roda em uma direção, o prêmio será $4$; girando-a na direção oposta, será $3$.
Por fim, no terceiro exemplo, a velocidade inicial ótima da roda é de $2$ graus por segundo. Nesse caso, a seta não conseguirá atravessar nenhuma fronteira entre setores, e o prêmio será $5$.
Nota
As soluções corretas para os testes em que $1 \le a \le b \le 1000$ serão avaliadas em até 50 pontos.