Une chaîne de télévision de divertissement diffuse l’émission «Колесо Фортуны». Pendant le jeu, les participants font tourner une grande roue divisée en secteurs. Chaque secteur porte un nombre. Quand la roue s’arrête, une aiguille spéciale désigne l’un des secteurs. Le nombre dans ce secteur détermine le gain du joueur.
Un jeune participant a remarqué que la roue ralentit en tournant parce que l’aiguille heurte des saillies situées entre les secteurs. Si la roue tourne à une vitesse angulaire de $v$ degrés par seconde et que l’aiguille heurte la saillie suivante en passant du secteur $X$ au secteur suivant, la vitesse angulaire actuelle diminue de $k$ degrés par seconde. Si $v\le k$, la roue ne peut pas franchir l’obstacle et s’arrête. L’aiguille désigne alors le secteur $X$.
Le jeune participant s’apprête à faire tourner la roue. Connaissant l’ordre des secteurs, il veut lui donner une vitesse initiale telle qu’après son arrêt, l’aiguille désigne le plus grand nombre possible. On peut faire tourner la roue dans les deux sens et lui donner une vitesse angulaire initiale allant de $a$ à $b$ degrés par seconde.
Écrivez un programme qui calcule le gain maximal à partir de la disposition des nombres dans les secteurs, des vitesses angulaires initiales minimale et maximale et de la diminution de vitesse au franchissement d’une frontière entre secteurs.
Entrée
La première ligne du fichier d’entrée contient un entier $n$, le nombre de secteurs de la roue ($3\le n\le100$).
La deuxième ligne contient $n$ entiers strictement positifs, chacun au plus égal à $1000$ : les nombres des secteurs. Ils sont donnés dans l’ordre des secteurs dans le sens horaire. Initialement, l’aiguille désigne le premier nombre.
La troisième ligne contient trois entiers $a,b,k$ ($1\le a\le b\le10^9$, $1\le k\le10^9$).
Sortie
Le fichier de sortie doit contenir un entier : le gain maximal.
Exemples
Entrée 1
5 1 2 3 4 5 3 5 2
Sortie 1
5
Entrée 2
5 1 2 3 4 5 15 15 2
Sortie 2
4
Entrée 3
5 5 4 3 2 1 2 5 2
Sortie 3
5
Remarque
Dans le premier exemple, on peut donner une vitesse initiale de $3$ ou $4$, ce qui permet à l’aiguille de franchir une frontière entre secteurs, ou une vitesse initiale de $5$, ce qui lui permet d’en franchir deux. Dans le premier cas, tourner dans un sens donne un gain de $2$ et tourner dans le sens opposé donne $5$. Dans le second cas, tourner dans un sens donne $3$ et dans l’autre donne $4$.
Dans le deuxième exemple, une seule vitesse initiale est possible : $15$ degrés par seconde. L’aiguille franchit alors sept frontières entre secteurs pendant la rotation. Tourner dans un sens donne un gain de $4$, et dans le sens opposé donne $3$.
Enfin, dans le troisième exemple, la vitesse initiale optimale est de $2$ degrés par seconde. L’aiguille ne peut alors franchir aucune frontière entre secteurs et le gain vaut $5$.
Remarque
Les solutions correctes pour les tests où $1\le a\le b\le1000$ seront évaluées sur 50 points.