Rohit Sharma was going through his scorecard of the previous world cup matches. He has played a total of N matches and has scored A₁, A₂, A₃, ..., A_N runs in the matches. During the selection process, Dhoni wants to know the average score of Rohit Sharma. So, Rohit Sharma calculates his average as follows:
He picks a match i (other than the last match) and replaces the score of A_i and A_i+1 matches with a single score of A_i - A_i+1 reducing the number of matches in scorecard by 1.
He continues the above process in the newly formed scorecard till the size of scorecard becomes 1.

Help Rohit to maximise his average score.

Input

First line contains an integer N, denoting the number of world cup matches. Next line contains N space separated integers, A₁, A₂, A₃,..., A_N.

Output

Print a single line containing the maximum average score possible.
Constraints
1 ≤ N ≤ 10^6
1 ≤ A_i ≤ 10^9

Example

Input:

4
1 5 2 3

Output:

1

Explanation

Example case 1.
Array: 1 5 2 3
Step 1: 1 3 3 (taking 2nd and 3rd score)
Step 2: 1 0 (taking 2nd and 3rd score)
Step 3: 1