Un canal de televisión de entretenimiento emite el programa «Колесо Фортуны». Durante el juego, los participantes hacen girar una gran rueda dividida en sectores. En cada sector hay escrito un número. Cuando la rueda se detiene, una flecha especial señala uno de los sectores. El número de ese sector determina el premio del jugador.
Un joven participante observó que la rueda se ralentiza mientras gira porque la flecha choca con los salientes de la rueda situados entre los sectores. Si la rueda gira con una velocidad angular de $v$ grados por segundo y, al pasar del sector $X$ al siguiente, la flecha choca con otro saliente, la velocidad angular actual de la rueda disminuye en $k$ grados por segundo. Si $v\le k$, la rueda no puede superar el obstáculo y se detiene. En ese caso, la flecha señala el sector $X$.
El joven participante se dispone a hacer girar la rueda. Conociendo el orden de sus sectores, quiere darle una velocidad inicial tal que, cuando se detenga, la flecha señale el mayor número posible. La rueda puede girar en cualquier dirección y se le puede dar una velocidad angular inicial de entre $a$ y $b$ grados por segundo.
Escribe un programa que, dada la disposición de los números en los sectores, las velocidades angulares iniciales mínima y máxima y la disminución de velocidad al cruzar un límite entre sectores, calcule el premio máximo.
Entrada
La primera línea del archivo de entrada contiene un entero $n$, el número de sectores de la rueda ($3\le n\le100$).
La segunda línea del archivo de entrada contiene $n$ enteros positivos, cada uno no mayor que $1000$, que son los números escritos en los sectores. Se dan en el orden de los sectores en sentido horario. Inicialmente, la flecha señala el primer número.
La tercera línea contiene tres enteros: $a$, $b$ y $k$ ($1\le a\le b\le10^9$, $1\le k\le10^9$).
Salida
El archivo de salida debe contener un entero: el premio máximo.
Ejemplos
Entrada 1
5 1 2 3 4 5 3 5 2
Salida 1
5
Entrada 2
5 1 2 3 4 5 15 15 2
Salida 2
4
Entrada 3
5 5 4 3 2 1 2 5 2
Salida 3
5
Nota
En el primer ejemplo son posibles las siguientes opciones: dar a la rueda una velocidad inicial de $3$ o $4$, lo que permite que la flecha cruce un límite entre sectores, o darle una velocidad inicial de $5$, lo que permite cruzar $2$ límites. En la primera opción, si se hace girar la rueda en una dirección, el premio es $2$, y si se hace girar en la dirección contraria, es $5$. En la segunda opción, al girar en una dirección el premio es $3$, y al girar en la otra, es $4$.
En el segundo ejemplo solo es posible una velocidad angular inicial: $15$ grados por segundo. En este caso, la flecha cruza siete límites entre sectores mientras gira la rueda. Si se hace girar en una dirección, el premio es $4$, y si se hace girar en la dirección contraria, es $3$.
Por último, en el tercer ejemplo la velocidad angular inicial óptima es $2$ grados por segundo. En este caso, la flecha no puede cruzar ningún límite entre sectores y el premio es $5$.
Nota
Las soluciones correctas para las pruebas en las que $1\le a\le b\le1000$ se evaluarán sobre un máximo de 50 puntos.