Wonha 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 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. Wonha 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'. Wonha 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 in the subsequence.
For example, let’s 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 Wonha and calculate the largest climb!
The input consists of T test cases. The number of test cases T is given in the first line of the input.
The first line of each test case contains a positive integer N (1 ≤ N ≤ 1,000), the number of measured points on the route.
The second line of each test case contains N positive integers Pi (1 ≤ Pi ≤ 1,000), the heights of measured points on the route.
The first and only line of output of each test case should contain the size of the largest climb. If the route in the input does not contain any climbs, output 0.
1 2 1 4 6
12 20 1 3 4 4 11 1
10 8 8 6 4 3
SourceCOCI 2010-2011 Round 6