Rohit Sharma was going through his scorecard of the previous world cup matches. He has played a total of N matches and has scored A1, A2, A3, ..., AN 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 Ai and Ai+1 matches with a single score of Ai - Ai+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.
First line contains an integer N, denoting the number of world cup matches.
Next line contains N space separated integers, A1, A2, A3,..., AN.
Print a single line containing the maximum average score possible.
Constraints 1 ≤ N ≤ 10^6 1 ≤ Ai ≤ 10^9
1 5 2 3
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