Time Limit: 3000 MS    Memory Limit: 65536 K 


Tomislav has recently discovered that hes completely out of shape. He actually becomes tired while walking down the stairs! One morning he woke up and decided to come in good shape. His favourite sport is cycling, so he decided to ride a tour on the local hills. The route he is taking is described as a sequence of N numbers which represent the height of the road at evenly spaced points of the route, from the beginning to the end of it. Tomislav is interested in the largest segment of the route which goes up the hill he has to ride, according to the information he has. Lets call such a segment a climb. Tomislav is too tired to bother about details, so he will only take into account the height difference of a climb, not its length. A climb is more strictly defined as a consecutive increasing subsequence of at least two numbers describing the road. The size of the climb is the difference between the last and first number n the subsequence. For example, lets consider a route described by the following sequence of heights: 12 3 5 7 10 6 1 11. Underlined numbers represent two different climbs. The size of the first climb is 7. The second climb is larger, with size 10. Points with heights 12 and 6 are not parts of any climb. Help Tomislav and calculate the largest climb!


The first line of input contains a positive integer N (1 N 1000), the number of measured points on the route. The second line of input contains N positive integers Pi (1 Pi 1000), the heights of measured points on the route.


The first and only line of output should contain the size of the largest climb. If the route in the input does not contain any climbs, output 0.

Sample Input

5 1 2 1 4 6 8 12 20 1 3 4 4 11 1 6 10 8 8 6 4 3

Sample Output

5 8 0

Second sample description

climbs are 12-20, 1-3-4, and 4-11. 1-3-4-4-11 is not a climb because sequence of numbers describing a climb has to be strictly increasing.


coci 2010/2011 contest6