Problem of The Day 23 December 2016 — Music on the Street

Music on the Street

There is a big music festival happening on Main street in Bytetown! We can consider this street to be along an infinite number line where, at every point on the line, some genre of music playing. More precisely, there are n points a0, a1 ,….an-1, which are borders between different genres of music. So, at every point from -∞ to a0, the first genre of music is playing (say, Techno). At every point from a0 to a1, the second genre of music is playing (say, Disco). This continues until the last genre of music (say, House), which is playing from an-1 to +∞. All coordinates are given in miles.Conor wants to visit this event. He plans to walk exactly m miles at a constant speed of 1 mile per hour in the positive direction. For each genre of music he passes, he wants to listen to it for a minimum of hmin hours (to determine whether he likes it or not) and a maximum of hmax hours (so he will not get bored).

Given n integers denoting the respective border points for each music genre and the values of m, hmin and hmax find and print an integer denoting the optimal location for Conor to start his walk through the festival such that all of his above requirements are satisfied.

Input Format

The first line contains a single integer, n, denoting the number of border points.
The second line contains n distinct space-separated integers describing the respective values of a0,a1,….an-1.
The third line contains three space-separated integers describing the respective values of m, hmin and hmax.

Constraints

• 1<=n<=106
• |ai| <=109 all ai are pairwise different and given in increasing order.
• 1 <= hmin <= hmax <= 109
• 1<=m<=109
• It’s guaranteed that at least one solution exists.

Output Format

Print a single integer denoting the possible start point for Conor’s walk. If there are several solutions, print any one of them.

Sample Input 0

2
1 3
7 2 3

Sample Output 0

-2

Explanation 0

If Conor starts at point -2, he will hear music in segment [-2,1] for 3 hours, segment [1,3] for 2 hours ,and segment [3,5] for his last 2 hours. Similarly, he could start walking at -1 and still satisfy all of his conditions.

Problem Link: Music on the Street

Solution will be posted tomorrow.