COCI 2007/2008, Contest #1

Task PRINOVA

Brojko and Brojana are happily married with N little boys. The boys are named with distinct even integers P₁, P₂, …, P_N.

Brojko and Brojana are expecting an addition to their family and have to come up with a nice name for the little girl. They have decided that the name will be an odd integer in the range [A, B]. Because they find all integers in that range equally beautiful, they have decided to choose the number which maximizes the distance to the name of the closest of the N boys.

More precisely, they seek an odd integer X ∈ [A, B] such that the expression min{|X − P_i|, i ∈ [1,N]} is as large as possible.

Write a program that determines the name for the little girl. If there are multiple solutions, output any of them.

Input

The first line contains an integer N (1 ≤ N ≤ 100), the number of boys.

The second line contains N distinct even integers, the names of the boys. The integers will be less than 10⁹.

The third line contains the integers A and B (1 ≤ A < B ≤ 10⁹), the range of names they are considering for the girl.

Output

Output an integer, the name for the little girl.

Examples

3
2 6 16
20 50

49

3
2 6 16
3 15

11

3
2 6 16
1 7

5

All Submissions
Best Solutions

Point Value: 7
Time Limit: 1.00s
Memory Limit: 32M
Added: Aug 09, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)