Today the teacher decided to assign a problem about finding the maximum possible average of a contiguous subarray ~(a_{i}, a_{i+1}, ..., a_{j-1}, a_{j}~ with ~0<i≤j≤N)~ for the whole class to solve. The problem asks the students to find a contiguous subarray with the highest possible average. ~Jack - J97~ is one of the students in the class, but due to playing too much and skipping classes, he couldn't solve this problem. So he decided to ask for your help. Let's help him out! </p>

Input:

• The first line contains an integer ~N~ ~(N ≤ 10^5)~, which is the number of elements in the array.
• The ~N~ lines contain ~N~ positive integers ~a_i~ ~(1≤a_i≤10^{30})~, which are the elements of the array.

Output:

• Print a single line containing the result of the problem, which is the maximum average of any contiguous subarray.

Sample Input

6
1 
1
1
3
3
3

Sample Output

3