Maximum Gap Query

You are given \(N\) strictly increasing non-negative integers \(a_1, a_2, \dots, a_N\) satisfying \(0 \le a_1 < a_2 < \cdots < a_N \le 10^{18}\). Your task is to compute the maximum difference between consecutive elements, i.e. find

\( \max_{1 \le i \le N-1} (a_{i+1} - a_i) \).

However, you are not allowed to read the entire sequence directly. Instead, you can obtain information about the sequence by using a provided query function MinMax(s, t, &mn, &mx) (or its equivalent in other languages), which, given the range \([s, t]\), returns the smallest and largest elements in the subsequence that lie within that range. In our simulation, the full sequence will be provided as input.

Your task is to implement a function findGap(T, N) that returns the maximum gap between consecutive elements. Note that \(T\) is the subtask number (either 1 or 2) and \(N\) is the length of the sequence.

Implementation Details:

• C/C++: Include the header gap.h and implement the function findGap(T, N) which calls the query function MinMax(s, t, &mn, &mx).
• Pascal: Use the unit graderhelperlib and implement a function findGap(T, N). The query function is MinMax(s, t, mn, mx) which works with parameters passed by reference.

For the purpose of this problem, you will read the full input and calculate the maximum gap directly.

inputFormat

The first line of input contains two integers: \(T\) (the subtask number) and \(N\) (the number of elements in the sequence).

The second line contains \(N\) space-separated strictly increasing non-negative integers \(a_1, a_2, \dots, a_N\).

outputFormat

Output a single integer --- the maximum value among \(a_{i+1} - a_i\) for \(1 \le i \le N-1\).

sample

1 5
0 1 2 4 8

4