2sec

Peasant Ion's only fortune is made up of N apple trees perfectly lined up in a row, apple trees which Ion has numbered from 1 to N.
For a while now, Ion has been feeling as if his strength is leaving him and he realizes he must give part of the apple trees to his 2 sons. But Ion can't forget how his younger son gave him a lot of heartache ever since he grew up so he decides the following:
- each of the two sons will receive a sequence of apple trees located on consecutive positions in the row of apple trees;
- the number of apple trees from his first son's sequence may differ from the number of apple trees of the second son's sequence, but each son will receive at least one apple tree;
- the younger son will receive apple trees that have lower numbers than the older son will;
- the difference between the profit of the older son's apple trees and the younger son's profit has to be maximal.
The profit made by an apple tree is calculated by Ion using complicated formulae which he perfected over the years.

Task
Write a program that determines this difference for Ion.

Input Data

Line one of input file 2sec.in contains a positive integer N representing the number of apple trees. The following line contains N positive integers, each separated by a space, the i-th number representing the profit made by the i-th tree.

Output Data

Output file 2sec.out will contain a single line with the maximum difference that can be obtained respecting Ion's requirements.

Constraints

1 < N < 1001001
-128 < the profit made by an apple tree < 128

Example