Tomislav has recently discovered that he's completely out of shape. He actually becomes tired while walking down the stairs! One morning he woke up and decided to get 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. Let's 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 strictly increasing subsequence of at least two numbers describing the road. The size of the climb is the difference between the last and first number in the subsequence.

For example, let's consider a route described by the heights \(12\), \(3\), \(5\), \(7\), \(10\), \(6\), \(1\), \(11\). The numbers \(3, 5, 7, 10\) and \(1, 11\) 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.

The first line of input contains a positive integer \(N\) (\(1 \le N \le 1000\)), the number of measured points on the route.

The second line of input contains \(N\) positive integers \(P_i\) (\(1 \le P_i \le 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\).

Second sample description: climbs are \(12\text{-}20\), \(1\text{-}3\text{-}4\), and \(4\text{-}11\). The sequence \(1\text{-}3\text{-}4\text{-}4\text{-}11\) is not a climb because a climb has to be strictly increasing.

riseoj 작성

출처 COCI 2010/2011 Contest 6