Wheel of Fortune

Interview

Time limit2sMemory limit512 MB

Summary

Given n sector values on a circular wheel, a slowdown k per boundary crossing, and an initial velocity in [a, b], find the largest sector value the arrow can stop on when spinning either direction.

Level: Medium5 of 10
Topics: Math, Implementation, Brute force, Array
Solved: No attempts yet

Problem

An entertainment television channel broadcasts a show called «Wheel of Fortune». During the game the contestants spin a large wheel divided into sectors. Each sector of the wheel has a number written on it. After the wheel stops, a special arrow points to one of the sectors. The number in that sector determines the contestant's prize.

A young contestant noticed that the wheel slows down while spinning because the arrow catches on the tabs between the sectors. If the wheel spins with angular velocity $v$ degrees per second, and the arrow, moving from sector $X$ to the next sector, catches on the next tab, then the current angular velocity of the wheel decreases by $k$ degrees per second. If $v \le k$ , the wheel cannot get over the obstacle and stops. In that case the arrow points to sector $X$ .

The young contestant is going to spin the wheel. Knowing the order of the sectors on the wheel, he wants to give the wheel an initial velocity such that after it stops the arrow points to the largest possible number. The wheel can be spun in either direction, and it can be given an initial angular velocity from $a$ to $b$ degrees per second.

Given the arrangement of the numbers in the sectors, the minimum and maximum initial angular velocity of the wheel, and the amount by which the wheel slows down when crossing a sector boundary, write a program that computes the maximum prize.

Input

The first line of the input file contains an integer $n$ , the number of sectors on the wheel ( $3 \le n \le 100$ ).

The second line of the input file contains $n$ positive integers, each not exceeding 1000: the numbers written in the sectors of the wheel. The numbers are given in the order in which the sectors follow clockwise. Initially the arrow points to the first number.

The third line contains three integers: $a$ , $b$ , and $k$ ( $1 \le a \le b \le 10^9$ , $1 \le k \le 10^9$ ).

Output

The output file must contain one integer: the maximum prize.

Notes

In the first example the following options are possible: the wheel can be given an initial velocity of 3 or 4, which makes the arrow cross one boundary between sectors, or an initial velocity of 5, which lets the arrow cross 2 boundaries between sectors. In the first option, if the wheel is spun in one direction the prize is 2, and if it is spun in the opposite direction the prize is 5. In the second option, if the wheel is spun in one direction the prize is 3, and if it is spun in the other direction the prize is 4.

In the second example only one initial angular velocity is possible: 15 degrees per second. In that case, as the wheel spins, the arrow crosses seven boundaries between sectors. Then if the wheel is spun in one direction the prize is 4, and if it is spun in the opposite direction it is 3.

Finally, in the third example the optimal initial angular velocity of the wheel is 2 degrees per second. In that case the arrow cannot cross a boundary between sectors at all, and the prize is 5.

Examples3

Example 1
Input
```
5
1 2 3 4 5
3 5 2
```
Expected output
```
5
```
Example 2
Input
```
5
1 2 3 4 5
15 15 2
```
Expected output
```
4
```
Example 3
Input
```
5
5 4 3 2 1
2 5 2
```
Expected output
```
5
```