Highest Elevation Gain

You are given an array of elevation measurements and several queries. For each query, which is given as a pair of indices (start and end), compute the highest elevation gain between two consecutive points within the segment. The elevation gain between two adjacent pixels is defined as the difference between the second value and the first value. Note that gains can be negative if the elevation decreases.

Input Format: The first integer n denotes the number of elevation measurements. The next line contains n integers representing the measurements. Following that, an integer q indicates the number of queries. Each of the next q lines contains two integers representing the start and end indices (inclusive) of a segment.

Output Format: For each query, output the highest elevation gain (i.e. the maximum difference between two adjacent measurements) separated by a space on a single line.

inputFormat

The input is read from standard input (stdin) and has the following format:

n
e1 e2 ... en
q
s1 e1
s2 e2
... (q lines total)

Where n is the number of elevation measurements, the second line has n space-separated integers, q is the number of queries, and each query consists of two integers representing the starting and ending indices of the segment.

outputFormat

Output a single line to standard output (stdout) containing the highest elevation gain for each query segment, separated by spaces.

5
2 3 5 1 4
2
0 2
1 4

2 3